37. backtracking and pseudo polynomial [14 1주차]

37. Backtracking and Pseudo Polynomial [14-1주차]

2024년 1월 14일 일요일

오후 5:11

<Backtracking>

어떤 문제를 풀기 위해 모든 경우의 수를 체계적인 순서로 중복되지 않게 시도해 보는 것.

 

 

<Pseudo Polynomial>

컴퓨터가 입력받는 실제 값은 0과 1로 구성된 비트이다. 따라서 알고리즘의 시간복잡도를 정확히 표현하려면 입력값이 몇 비트인지를 기준으로 식을 세워야 한다.

 

예를 들어, 소인수분해를 하는 알고리즘을 살펴보자.

 

primeFactor(int n) {

r[]

for(i = 2; i<n; i++) {

n이 i로 나누어떨어지지 않을 때까지 n /= i 를 실행;

r[i]에 n을 i로 나눈 횟수 저장

}

return r;

}

 

 

위 코드는 O(n)시간이 걸린다.

이는 다항 시간 알고리즘처럼 보이지만, 사실 그렇지 않다. n이 비트 수가 아니라 입력값 자체이기 때문이다.

 

입력의 비트 수를 b라고 하면 b는 대략 다음과 같다.

b = logn -> 2^b = n

 

따라서 O(n)을 비트로 표현하면 O(2^b)이고, 소인수분해 알고리즘은 지수 시간이 걸림을 알 수 있다.

 

만약 컴퓨터가 1진법을 사용했다면(5를 11111로 표현) 위 알고리즘은 다항 시간에 작동했을 것이다. 이처럼 실제로는 지수 시간에 실행되지만, 1진법을 사용한다고 가정했을 때 다항 시간에 작동하는 알고리즘을 pseudo polynomial(의사 다항) 시간에 실행된다고 한다.

 

동적계획법에서 배웠던 동전 거스름 돈 알고리즘도 의사 다항 시간에 실행되는 예이다.

 

 

<Backtracking - N-Queen>

N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 올려놓는 경우의 수를 구하는 문제.

(퀸은 상하좌우와 대각선 총 8방향으로 거리 제한 없이 이동할 수 있다)

 

N=8일 때, 64개 칸에 8개의 퀸을 배치하는 경우의 수는 총 ₆₄C₈가지.

그러나 한 행에 퀸이 하나씩만 배치될 수 있으므로, 8칸 배열에 각 행에 퀸이 몇 번째 줄에 배치되는지를 저장한다면, 경우의 수는 8⁸가지가 된다. 같은 열에 퀸이 두 개 이상 오지 못하도록 하면 8!가지가 되고 퀸의 대각선 방향 공격 경로까지 고려하면 경우의 수는 더욱 줄어든다.

 

 

<N-Queen 알고리즘>

 

1.     첫 번째 행에 퀸 하나를 배치하고, 퀸이 공격할 수 있는 위치를 표시한다.

2.     다음 행의 공격받지 않는 위치에 퀸을 배치하고, 퀸에게 공격받을 수 있는 위치를 갱신한다.

3.     2를 반복한다.

4.     만약 한 행의 모든 위치가 공격받는 위치여서 퀸을 배치할 수 없다면 위 행의 퀸을 다른 위치로 옮겨 다시 시도한다.

5.     마지막 행까지 퀸이 배치된다면 경우의 수를 증가시킨다.

6.     아래 행부터 퀸의 위치를 옮겨 가며 모든 경우를 찾는다.

 

 

<Pseudo Polynomial - 막대 자르기>

길이 i인 막대기의 가치 V[i]가 입력으로 주어졌을 때, 길이 N인 막대기를 잘 나누어서 최대 가치로 나누는 문제

 

ex) N=4일 때

 

이를 동적계획법을 통해 풀 수 있다.

D[i]를 길이 i인 막대기를 나눌 때 최대 가치라 하고, D[0]부터 시작하여 D[N]을 구해 보자.

 

1.     D[0] = 0

2.     D[1] = max(D[0] + V[1])

3.     D[2] = max(D[0] + V[2],  D[1] + V[1])

4.     D[3] = max(D[0] + V[3],  D[1] + V[2],  D[2] + V[1])

5.     D[3] = max(D[0] + V[4],  D[1] + V[3],  D[2] + V[2],  D[3] + V[1])

…

 

일반화하면

D[i] = max(D[i - j] + V[j]) (1<=j<=i)

 

 

<Pseudo Polynomial - 합 분해>

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제.

 

D[i][j] 를 i개의 수를 사용해서 j를 만드는 경우의 수라고 한다.

j = a₁ + a₂ + … + a_i

 

D[i][j]의 값을 마지막에 더하는 수 a_i가 j인 경우, j-1인 경우, j-2인 경우, …, 0인 경우로 나누어 구한다고 하면

D[i][j] = sum(D[i-1][k]) (0<=k<=j)

가 성립한다.

 

따라서 D[i-1][]을 먼저 구한 뒤 그 값을 이용하여 D[i][]를 구할 수 있다.

테이블이 N x K칸이고 한 칸을 계산하는 데 최대 N개의 수를 계산하므로 시간복잡도는 O(N²K)가 걸린다.

그러나 이전 칸을 채울 때 참조하는 부분을 다음 칸이 참조한다는 점(D[3][1] = 1+2 를 채울 때의 계산값이 D[3][2] = 1+2+3 에도 사용됨)을 이용하면 O(NK) 시간이 걸린다.