궤도

문제 풀이 입력을 어떻게 처리하여 어떤 순서로 스도쿠의 빈공간을 채워나갈지 고민을 많이했다. 처음에는 1행->9행으로 값을 채우고 그 다음에 1열->9열로 값을 채우고 마지막으론 구역별로..?라고 생각하다가 너무 복잡해질 것 같다는 생각이 들었다. 그러다 내가 실제로 스도쿠를 볼 때 어떻게 푸는지 생각했다. 보통 사람들은 먼저 빈공간을 찾아가서 그 공간의 행, 열, 구역을 한번에 확인한 뒤 값을 채워나간다. 그럼 코드도 이런식으로 짜면되지 않을까? 싶었다. 입력을 받으면서 빈공간을 봐둔 다음에 각각의 빈공간마다 1~9를 넣어보면서 그 공간의 행, 열, 구역의 숫자와 비교하면 될 것 같았다. 이 아이디어를 떠올리니 나머지는 크게 어렵지 않았다. 소스코드 #include using namespace std;..

문제 풀이 N-Queen 문제는 백트래킹의 대표적인 문제이다. 근데 난 얘가 너무 어렵다... 이런 체스판에 퀸을 놓고 이 퀸들이 서로 공격할 수 없게 놓는 문제이다. 퀸은 가로세로대각선으로 이동할 수 있으니 어떠한 퀸들도 같은 행열대각선에 위치하지 않도록 배치해야 한다. 소스코드 #include using namespace std; const int SIZE = 15; int n, ans; int check[SIZE]; bool promising(int num) { int idx = 0; while (idx < num) { //이미 놓여있는 모든 퀸에 대해 if (check[num] == check[idx] || abs(check[num] - check[idx]) == (num - idx)) //같은 ..

문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com myunji.tistory.com/199?category=1154147 [백준] 15651번 : N과 M (3) 문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?categor..

문제 풀이 myunji.tistory.com/198?category=1154147 [백준] 15650번 : N과 M (2) 문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇.. myunji.tistory.com 번호로는 위 문제의 다음이지만 사실 이 문제가 더 간단하다. 왜냐하면 현재 노드를 기억해 둘 필요도 없고...눈치가 빠른 사람은 알겠지만 입력에 따른 출력 갯수가 N^M이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int a..

문제 풀이 myunji.tistory.com/73?category=1154147 [백준] 15649번 : N과 M (1) 문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 myunji.tistory.com 이 문제를 약간 응용한 문제이다. 오름차순을 구현하려면 어떻게 해야할까? 현재 노드의 값을 기억해두면 될 것이다. 소스코드 #include using namespace std; const int MAX = 8; int N, M; int arr[MAX]; void backNM(int cnt, int flag) { //오름차순 위해 현재 노드 저장하는 flag 추..

문제 풀이 백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 표현할 때 트리를 많이 사용하는데 이 문제도 간단히 트리로 나타내면 이런 모습이다. visited를 true로 하느냐 false로 하느냐에 따라 트리의 아래로 가거나 위로 올라갈 수 있다. 이 문제도 노드들을 방문하며 visited를 갱신하고, 배열에 값을 넣는다. 배열의 크기가 M이 되면 트리 탐색을 끝내고 배열에 있는 수를 출력한다. 재귀함수는 아무래도 머리로 따라가기가 좀 까다로우니 그림을 그려가며 공부하면 좋을 것이다. 소스코드 #include using namespace std; const int MAX..