그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 미완성된 스도쿠 판이 입력으로 주어질 때, 스도쿠판을 완성해서 출력하는 문제이다. 이 문제는 일단 N-Queen과 굉장히 유사하다. N-Queen문제를 생각해보면 보드에서 모든 자리를 살펴보는데 각 자리에 대해서 queen을 놓을 수 있는지 없는지 판단한 뒤, 놓을 수 있는 경우에는 놓고 지나거나 안 놓고 지나가고, 놓을 수 없는 경우에는 안놓고 지나간다. 이러한 백트래킹은 다음과 같은 논리..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 정수 N이 주어질 때, N번째 감소하는 수를 출력하는 문제이다. 321, 9741, 987654321 등은 감소하는 수의 예시다. 일단 N번째 수를 찾으려면 그 전의 수부터 찾아가면서 백트래킹으로 N번째 수에 도달하는 방법을 사용해야 함을 알 수 있다. 백트래킹을 어떻게 수행할지 결정하기 위해서는 우선, 어떤 규칙으로 수를 카운팅 해야하는지 수열의 규칙을 분석해봐야 한다. 이 문제에..