[교내 강의 조교 일지 03] Dynamic Programming (1)

강의 내용

[강의 노트]

DP의 기초적인 내용들과 약간의 응용들을 다루었다.

피보나치 수열의 다양한 구현 (top down, bottom up)으로 dp에 대한 기본 구현을 강의하고,

LIS등 어려운 dp 문제 맛보기도 살짝 하였다.

이후 피보나치 N번째 항 logN에 구하기 등 행렬의 분할 정복을 이용하는 테크닉도 소개하였다.

 

강의 과제

피보나치는 $F_n = F_{n-1} + F_{n-2}$라는 매우 간단한 수식으로 이루어진 dp이다.

따라서 이번 과제는 여기서 항 하나만 더 추가한 $F_n = F_{n-1} + F_{n-2} + F_{n-3}$ 이라는 수식에서 시작해서 살짝씩 변형해가며 3개의 과제 문제를 만들었다.

 

A. 돌다리도 두드려보고 건너야 한다 (Easy)

[문제] [정답 코드]

$N$개의 돌로 이루어진 다리를 건너는 경우의 수를 물어보는 문제이다. 한 번에 최소 1칸, 최대 3칸을 뛸 수 있다.
따라서 여기서 $F_n = F_{n-1} + F_{n-2} + F_{n-3}$ 수식이 바로 나오지만, 여기서 살짝 변형을 하였다.

총 $N$개의 돌 중 $K$개의 돌은 밟지 못한다는 조건이다.

따라서 만약 밟을 수 없는 돌이라면 $F_n = 0$으로만 해 주어도 바로 풀 수 있는 문제이다.

시간복잡도는 $O(N)$이다.

여기서 주의할 점은 다리에 있는 돌의 개수가 $N$개이므로, 건너가는 경우의 수는 $F_{N+1}$에 해당한다는 것이다.

B. 돌다리도 두드려보고 건너야 한다 (Normal)

[문제] [정답 코드]

이번 문제에서는 모든 돌을 밟을 수 있지만 $N$의 범위를 대폭 늘렸다.

따라서 $O(\log N)$으로 풀어야 하는 문제이다.

피보나치 N번째 항 구하기에서 했던 비슷한 방법으로 풀면 된다.

따라서 정답은 아래의 수식으로 구할 수 있다.

$ \begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \end{bmatrix}  = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}^N \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$

 

위 수식을 분할정복을 이용해서 계산하면 $O (\log N)$에 풀 수 있다.

C. 돌다리도 두드려보고 건너야 한다 (Hard)

[문제] [정답 코드]

가는 경우의 수만 세는 건 쉬우니 갔다가 돌아오는 경우의 수도 세면 재미있을 것 같다고 생각해서 떠올렸다.

그냥 돌아오면 재미가 없으니 가면서 밟은 돌은 돌아올 땐 밟지 못하도록 해보았다.

그런데 돌아오는 방식을 정하는 게 쉽지 않았다. 돌아오는 것도 1칸에서 3칸 사이로 돌아오라고 했을 때는 답을 구하는 게 어려웠다. 따라서 돌아올 땐 칸의 제한을 없애버리면 어떨까 하고 생각했는데, 생각보다 괜찮은 것 같아 이렇게 출제를 했다.

 

핵심 아이디어는 돌아올 때, 경우의 수를 세기 위해서 알아야 하는 정보는 남의 돌의 개수라는 것이다.

즉, 몇 번째 돌이 남아있는 지는 중요하지 않고 그냥 몇 개의 돌을 밟을 수 있는지만 알면 된다.

그 이유는, 돌아올 때 모든 돌을 밟을 수도 있고, 아무 돌을 안밟고 돌아올 수도 있다. 즉, 임의의 돌을 밟거나 안밟거나를 내 맘대로 정할 수 있다는 것이다. 따라서 밟을 수 있는 돌이 $n$개라면, 돌아오는 경우의 수는 $2^n$인 것이다.

 

이제 원래 문제로 돌아오자. 우리는 돌다리를 건너고 돌아오는 경우의 수를 구해야 한다. 돌다리에서 돌아올 때 남아있는 돌의 수를 알아야 하므로, 돌다리를 건너는 중에 몇 개의 돌을 밟았는 지도 알아야 한다. 따라서 이전 두 문제에서는
$dp[k] =$ $k$번째 돌까지 이동하는 경우의 수
로 단순하게 정의했다면, 이번에는
$dp[n][k] = $ 총 $n$개의 돌을 밟아서 $k$번째 돌까지 이동하는 경우의 수
로 정의를 해야 한다. 이렇게 dp를 정의한 다음에 점화식에 따라 계산하면 된다.

점화식은 $dp[n][k] = dp[n-1][k-1] + dp[n-1][k-2] + dp[n-1][k-3]$이다.

 

이렇게 점화식을 모두 계산했다면, 돌다리를 건너가는 경우의 수를 모두 계산한 것이다. 이제 돌다리에서 돌아오는 경우의 수를 계산하면 된다. 돌아오는 경우의 수는

$\sum_{n=1}^{N} dp[n][N+1] \times 2^{N-n}$이다.