동적 계획법(Dynamic Programming)란?

문제를 작은 부분 문제로 나누고, 부분 문제의 답을 표에 기록하여 재사용함으로써 같은 계산의 반복을 피하는 알고리즘 설계 방법. 배낭 문제, 동전의 최소 개수, 최장 공통 부분 수열, 최단 경로 등에 쓰인다.

일본어 명칭: 動的計画法

동적 계획법(Dynamic Programming)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 3개에 나와요.

사고방식: 겹치는 부분 문제를 한 번만 푼다

피보나치 수를 fib(n) = fib(n−1) + fib(n−2)로 그대로 재귀 계산하면 같은 값을 몇 번이고 다시 계산하게 되어, 호출 횟수가 지수적으로 늘어납니다(fib(30)에서 약 269만 회). 동적 계획법에서는 한 번 구한 부분 문제의 답을 표에 기록하고, 다음부터는 표를 찾아보기만 합니다. 이렇게 하면 fib(n)은 n에 비례하는 수고로 구해집니다. 사용할 수 있는 조건은 큰 문제의 최적해가 작은 부분 문제의 최적해로 조립된다는 것(최적 부분 구조)과, 같은 부분 문제가 여러 번 나타난다는 것(중복되는 부분 문제)입니다.

메모이제이션과 표 채우는 방법

구현에는 재귀의 형태 그대로 계산한 결과를 기억해 두는 메모이제이션(하향식)과, 작은 부분 문제부터 차례로 표를 채워 가는 상향식의 두 가지 방법이 있습니다. 예를 들어 0/1 배낭 문제에서는 '물건 i까지를 사용하여 용량 c 이내에서 얻을 수 있는 최대 가치'를 표로 만들고, 물건을 넣는 경우와 넣지 않는 경우 중 큰 쪽을 고르면서 채워 갑니다. 물건 수를 n, 용량을 W라 하면 수고는 O(nW)입니다. 동전의 최소 개수 문제도 0엔부터 목표 금액까지 각 금액의 최소 개수를 차례로 표로 만들면 풀 수 있습니다.

탐욕 알고리즘과의 차이와 응용

탐욕 알고리즘은 그 시점에서 가장 좋은 선택을 하나 골라 앞으로 나아갈 뿐이므로 빠르지만, 문제에 따라서는 최적해가 되지 않습니다. 1엔·4엔·6엔 동전으로 8엔을 지불하는 경우, 탐욕 알고리즘은 6 + 1 + 1의 3개이지만 동적 계획법이라면 4 + 4의 2개가 구해집니다. 동적 계획법은 문자열의 편집 거리나 최장 공통 부분 수열(diff 명령), DNA 서열의 정렬(alignment), 음성 인식의 비터비 알고리즘, 모든 정점 간의 최단 경로를 구하는 플로이드-워셜 알고리즘 등 폭넓게 쓰이고 있습니다.

도전해 보기: 동적 계획법(Dynamic Programming) 관련 문제

피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?

A6회
B9회
C15회

정답과 해설 보기

정답: C. 15회

fib(n)의 호출 횟수를 C(n)이라 하면 C(0) = C(1) = 1, C(n) = 1 + C(n−1) + C(n−2)이므로 C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15입니다. 같은 값을 몇 번이고 다시 계산하기 때문에 횟수는 n에 대해 지수적으로 늘어나며, fib(30)에서는 약 269만 회가 됩니다. 계산한 값을 표에 기억해 두는 메모이제이션(동적 계획법)을 사용하면 계산은 fib(0)~fib(5)의 6가지로 끝나고, 호출도 9회(2n − 1)로 줄어듭니다. 6회는 서로 다른 인수의 수, 9회는 메모이제이션을 한 경우의 호출 횟수입니다.

1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으로 정했을 때의 개수와 최소 개수의 관계로 올바른 것은?

A탐욕 알고리즘으로도 최소인 2개가 된다
B탐욕 알고리즘으로는 3개가 되어, 최소인 2개가 되지 않는다
C탐욕 알고리즘으로는 3개가 되며, 이것이 최소이다

정답과 해설 보기

정답: B. 탐욕 알고리즘으로는 3개가 되어, 최소인 2개가 되지 않는다

탐욕 알고리즘에서는 먼저 6엔을 1개 쓰고, 나머지 2엔을 1엔 2개로 지불하므로 3개입니다. 그러나 4엔을 2개 쓰면 2개로 지불할 수 있습니다. 이처럼 탐욕 알고리즘은 그 시점에서 가장 좋은 선택을 쌓아 갈 뿐이므로, 동전의 조합에 따라서는 최적이 되지 않습니다. 동적 계획법으로 '0엔부터 8엔까지 각 금액을 지불하는 최소 개수'를 작은 금액부터 차례로 표로 만들면 반드시 최소 개수가 구해집니다. 덧붙여 1, 5, 10, 50, 100, 500엔 같은 일본 동전의 조합에서는 탐욕 알고리즘으로도 항상 최소가 됩니다.

자주 묻는 질문

동적 계획법과 분할 정복은 어떻게 다른가요?

둘 다 문제를 부분 문제로 나누지만, 병합 정렬 같은 분할 정복에서는 부분 문제가 겹치지 않으므로 표에 기록할 필요가 없습니다. 동적 계획법은 같은 부분 문제가 여러 번 나타나는 경우에 답을 기록하여 재사용한다는 점이 다릅니다.

동적 계획법의 약점은 무엇인가요?

표의 크기만큼 기억 영역과 수고가 필요합니다. 배낭 문제의 O(nW)는 용량 W의 값에 비례하므로, W가 매우 크면 현실적이지 않게 됩니다. 필요한 부분만 기록하거나 바로 앞 행의 결과만 남기는 등으로 기억 영역을 줄이는 궁리를 합니다.

해설 속 동적 계획법(Dynamic Programming)

계산한 값을 표에 기억해 두는 메모이제이션(동적 계획법)을 사용하면 계산은 fib(0)~fib(5)의 6가지로 끝나고, 호출도 9회(2n − 1)로 줄어듭니다.
피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1)…
동적 계획법으로 '0엔부터 8엔까지 각 금액을 지불하는 최소 개수'를 작은 금액부터 차례로 표로 만들면 반드시 최소 개수가 구해집니다.
1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으…
동적 계획법에서는 '용량 c까지로 달성할 수 있는 최대 가치'를 물건마다 표로 갱신하여, 물건 수 n과 용량 W에 대해 O(nW)로 최적의 값을 구합니다.
용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 …