꾸준히 하기/알고리즘 12
-
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 예제 입력 예제 출력 2 3 1 11 3 7 7 63 1 0 0 0 4 7 7 63 10 511 511 262143 10 512 512 786432 문제 바로가기 탐색 방법 해당 문제를 분할하여 재귀 알고리즘으로 값을 구하도록 구현했다. 작은 상자로 나눠 어떤 규칙에 따라 값이 증가하는지 찾으려고 노력했다. 먼저 2X2 박스씩 확인하여 규칙을 찾았다. 행과 열이 2배가 되면, 상자 안의 값이 4의 배수로 늘어..
-
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 예제 입력 예제 출력 8 92 문제 바로가기 체스판 체스판을 일차원 배열로 생성 및 초기화한다. 만약 chess[1] = 2라고 한다면, 1행 2열에 체스말을 둔 것이라 생각하면 된다. 탐색 방법 전형적인 백트래킹(Backtracking) 문제이다. N X N 체스판에 N개의 말이므로, 모든 행에 퀸이 놓여져 있어야 한다. 또한 퀸들이 같은 행에 있거나 대각선 위치에 있으면 안된다. 차례대로 말을 두면서 조건에 일치하면 해당 열에 말을 두고 다음 행으로 넘어감, 일치하지 않으면 다음 열을 확인해야 한다. 백트래킹 (Backtrack..
