문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹 문제이다. 체스판에서 퀸이 공격할 수 있는 위치는 상하좌우와 대각선상의 모든 위치이다. 4x4 체스판의 (0,0) 위치에 퀸 하나를 두었을 때, 퀸이 공격 가능한 위치를 그림으로 나타내면 다음과 같다. 즉, nxn의 판에서 퀸 n개를 모두 서로 공격할 수 없는 위치에 놓으려면 각 퀸들이 상하좌우 대각선 중 어느 곳에도 위치해서는 안된다. 이 조건을 분해해보면, 1. 각 행에는 무조건 퀸이 존재..

문제 https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 풀이 백트래킹 방법으로 문제를 해결할 것이다. 백트래킹 방법은 가지를 탐색하다가 옳지 않으면 바로 다른 가지로 넘어간다. 이 문제에서는 첫번째 자리의 수부터 k+1번째 자리의 수까지 추가해나가며 탐색한다. 탐색 중에 j번째 자리에 넣을 수가 이전 수와의 부등호 조건에 맞지 않으면(ex- 부등호가