Backtracking and Pseudopolynomial

• Backtracking: 모든 경우를 다 따지는데 cutoff(이런 경우는 안 보겠다고 규칙을 정하는 것)를 함

• Pseudopolynomial: 알고리즘의 시간복잡도를 계산할 때 시간복잡도가 input의 크기가 아닌 input의 값으로 결정되는 알고리즘. O(N)이니까 polynomial처럼 보이지만, polynomial이 아니다! sorting의 O(NlogN) 시간에서 N은 입력한 값이 아니라 입력의 사이즈가 N이기 때문이다.

N-Queen

Eight queens puzzle

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

N=8인 경우를 생각해보자. 일단 가장 간단하고 무식한 방법은 모든 경우의 수를 다 고려해 보는 것이다.

1st Try

일단 8 x 8 보드이므로 퀸은 8개, 자리는 64개가 있다. 8개의 퀸을 64개의 자리에 놓을 수 있기 때문에 8쌍의 퀸의 위치에 대해 64^8가지의 경우가 발생한다. 그리고 각각의 쌍에 대해 공격할 수 있는지를 따져야 하니까 전체 시간은 (64^8)*8*7이다.

2nd Try

조금 더 빠르게 계산하는 방법은 겹치는 경우를 제거하는 것이다. 그러면 64개의 자리 중 8개를 고르므로 64^8 대신 64C8을 사용하여 전체 64C8 * 8 * 7 시간이 걸린다. 조금 더 빨라지겠지만 여전히 많이 느리다. 그리고 이 방식은 구현하기도 만만치 않다.

3rd Try

각 row에 하나씩 배치해보자. 한 row에 두 개의 퀸이 있을 이유가 없기 때문이다. 그러면 각 row에는 8개의 col이 있으므로 퀸을 배치하는 경우의 수는 8^8이다. 따라서 전체 (8^8)*8*7 시간이 걸리는데 이는 (2^30)정도의 시간임. 아마 돌아가긴 할 거다..

4th Try

그럼 이제 cutoff까지 해보자. 그리고 재귀를 활용할 것이다.

일단 8개짜리 배열 N을 하나 만들고, 현재 row의 위치를 알려주는 변수 i를 선언한다. i는 내가 지금 몇 번째 row에 퀸을 배치해야 하는지를 알려준다. 그리고 내가 배치해야 하는 row의 위쪽은 이미 배치가 되어 있다.

배열을 활용하면 이전 값들을 가지고 현재 row에서 놓을 수 있는 자리들을 cutoff 할 수 있게 된다.

예를 들어 row 1, 2, 3에서 다음과 같이 퀸들이 배치되었다고 하자.

그럼 네 번째 row에서 퀸을 놓을 수 있는 자리는 2, 7, 8번째 col이므로, 2, 7, 8에 대해서만 재귀를 돌리면 된다. cutoff가 많이 되기 때문에 생각보다 빨리 끝난다.

N=4로 작게 잡아 전체 풀이과정을 보자.

배열

? 칸에 배열 원소 값들이랑 같은 값이 오면 안 되고, 절댓값이 차이가 거리랑 같은 경우도 오면 안 된다. 그래서 3에 배치했다고 해보자.

배열

올 수 있는 값이 없다. 그래서 3이 아니라 4에 배치해야 할 것 같다.

이번에는 세 번째 row에 퀸을 넣을 수 있다. 그러나 두 번째 col에 퀸을 놓을 경우 마지막 row에서 퀸을 놓을 수 없게 된다.

대각선 체크하는 방법

가로줄에 대해서는 한 줄에 하나씩 놓는 방식으로 처리할 수 있다.

동전 교환

N개의 동전 단위 C[i]가 있고 각 동전의 개수는 무한할 때 W원을 동전으로 바꿔주기 위해 필요한 최소 동전의 개수

2, 5, 10원짜리 동전으로 376원을 만들어보자. 2원은 0 - 188개, 5원은 0 - 75개, 10원은 0 - 37개 필요하므로 188x75x37가지의 경우가 발생한다. 만약 동전의 종류가 늘어나기라도 한다면?? 거의 O(W^N)의 시간복잡도를 가진다고 보면 됨

그러나 DP로 풀면 O(WN) 시간 안에 풀 수 있다. N이긴 하지만 W가 곱해져있기 때문에 polynomial은 아니고 pseudopolynomial임.

1, 4, 6원짜리 동전을 사용해 8원을 만들어보자. 먼저 모든 경우를 다 계산했을 때이다.

ans = min(8, 5, 3, 2) = 2

점화식 유도

D[i]: i원을 바꾸어주기 위해 필요한 동전의 최소 개수

배열의 크기가 W이고, 배열의 원소마다 계산하는데 N시간이 걸림

동전의 종류가 2원, 5원, 9원이 있는 상황에 대해 생각해 보자.

• 0원을 만드는데 드는 동전의 개수: 0개

  i	0	1	2	3	4	5	6	7	8	9	10
  D	0

• D[1] = 불가능 (충분히 큰 수) 1원은 주어진 동전으로 만들 수 없다.

  i	0	1	2	3	4	5	6	7	8	9	10
  D	0	X

• D[2] = D[0] + 1 = 1
  D[2-2], D[2-5], D[2-9]가 가능한 값인지 확인하고 그 중 가장 작은 값에 1을 더해준다.

  i	0	1	2	3	4	5	6	7	8	9	10
  D	0	X	1

• D[3] = D[1] + 1 = 불가능 (D[1]이 불가능하기 때문)

  i	0	1	2	3	4	5	6	7	8	9	10
  D	0	X	1	X

• D[10] = 2

  i	0	1	2	3	4	5	6	7	8	9	10
  D	0	X	1	X	2	1	3	2	4	1	2

막대기 자르기

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

N-1개의 cut point가 있으므로 전체 2^(N-1)개의 경우가 발생한다.

예제

일 때, 가능한 모든 경우에 대해 나누어 보면

• 1, 1, 1, 1 -> 가치 4
• 1, 1, 5 -> 가치 7
• 1, 8 -> 가치 9
• 5, 5 -> 가치 10
• 9 -> 가치 9 answer = max(4, 7, 9, 10, 9) = 10

일반화

D[i]: 길이 i인 막대기를 나눌 때까지 최대 가치 가능한 막대기의 길이를 맨 뒤에 두는 방향으로 생각해보자.

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

일반화하면 D[i] = max(D[i-j]+V[j]) (1<=j =i)

합 분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제 a1 + a2 + … + ak = N

K개의 정수가 모두 0 - N까지의 값을 가지므로, 하나씩 다 계산해보면 O((N^k) * k)의 시간복잡도를 갖는다.

이를 pseudopolynomial로 줄이면 O(k*(N^2)) 시간에 문제를 풀 수 있다.

Pseudopolynomial

2개의 숫자를 이용해 0, 1, 2, 3을 만드는 경우의 수를 이미 알고 있다고 가정해보자.

• 0을 만드는 경우: 0+0
• 1을 만드는 경우: 0+1, 1+0
• 2를 만드는 경우: 0+2, 1+1, 2+0
• 3을 만드는 경우: 0+3, 1+2, 2+1. 3+0

그러면 이를 가지고 3개의 숫자를 사용해 3을 만드는 경우의 수를 구할 수 있다.

• 0+0 + 3
• 0+1 + 2
• 1+0 + 2
• 0+2 + 1
• 1+1 + 1
• 2+0 + 1
• 0+3 + 0
• 1+2 + 0
• 2+1 + 0
• 3+0 + 0

일반화

D[i][j]: i개의 숫자를 사용해 j를 만드는 경우의 수 D[i][j] = sum(D[i-1][j-k]) (0<=k<=j)