Dynamic Programming
재귀호출과 메모이제이션
피보나치 수열
- 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치 수열이라 한다
- 피보나치 수열의 i번 째 값을 계산하는 함수 F를 정의하면
- F0 = 0, F1 = 1
- Fi = Fi-1 + Fi-2 For i >= 2
- 피보나치 수열의 i 번째 항을 반환하는 함수는 재귀함수로 구현 가능하다
피보나치 수를 구하는 재귀함수
fibo(n)
if n < 2
return n;
else
return fibo(n-1) + fibo(n-2);앞의 함수처럼 구현하게 되면 엄청난 중복 호출이 존재하게 된다.
그렇다면 중복을 피할 수 있는 방법이 있을까?
메모이제이션(memoization)
- 메모이제이션은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다.
- 동적 계획법의 핵심이 된다.
- 'memoization'은 글자 그대로 해석하면 '메모리에 넣기'라는 의미
메모이제이션 방법을 적용한 피보나치
memo를 위한 배열을 할당하고, 모두 0으로 초기화
memo[0]을 0으로, memo[1]은 1로 초기화
fibo1(n)
IF n >= 2 AND memo[n] = 0
memo[n] = fibo1(n-1) + fibo1(n-2)
return memo[n]메모이제이션의 한계..?
- 추가적인 메모리 공간이 필요
- 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우 발생 가능
동적 계획법
- 동적 계획법(Dynamic Programming)은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
- 동적 계획법은 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법
- 동적 계획법을 적용하려는 문제는 다음과 같은 요건은 항상 만족해야 한다
- 중복 부분문제 구조(Overlapping subproblems)
- 최적 부분문제 구조(Optimal substructure)
중복 부분문제 구조
- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결(순환적인 관계를 명시적으로 표현하기 위해 DP에서는 일반적으로 점화식을 사용)
- DP는 문제의 순환적인 성질때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 저장공간에 저장하게 된다
- 이렇게 저장된 해들이 다시 필요할 때마다 해를 얻기 위해 재계산하지 않고 참조를 통해 중복된 계산을 피하게 되는 방법
최적 부분문제 구조
- DP가 최적화에 대한 어느 문제에나 적용 가능한 것은 아님
- 주어진 문제가 최적화의 원칙을 만족해야만 DP를 효율적으로 적용이 가능하다
- 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것. DP의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용해 구하기 때문
분할정복 VS 동적 계획법
분할정복
- 연관 없는 부분 문제로 분할
- 부분문제를 재귀적으로 해결
- 부분문제의 해를 결합한다
- 병합정렬, 퀵 정렬
DP
- 부분 문제들이 연관이 없으면 적용 불가능. 즉 부분 문제들은 더 작은 부분 문제들을 공유
- 모든 부분 문제를 한번만 계산하고 결과를 저장하고 재사용한다
DP에는 부분 문제들 사이에 의존적 관계가 존재
- ex) E,F,G의 해가 C를 해결하는데 사용되어지는 관계가 있다
이러한 관계는 문제에 따라 다르고, 대부분의 경우 뚜렷하게 보이지 않아 함축적인 순서라고 한다
분할 정복은 하향식 방법으로, DP는 상향식 방법으로 접근
3단계로 나뉘어지는 DP 적용
-
최적해 구조의 특성을 파악
- 문제를 부분문제로 나누기
-
최적해의 값을 재귀적으로 정의
- 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의
-
상향식 방법으로 최적해의 값을 계산
- 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
- 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다(상향식 방법)
피보나치 수 DP적용
- 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어짐
- 문제를 부분 문제로 분할
- 점화식으로 정의
- 가장 작은 부분문제부터 해를 구한다. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.
fibo_dp(n)
f[0] = 0
f[1] = 1
for i in 2 -> n
f[i] = f[i-1] + f[i-2]
return f[n]재귀 알고리즘과는 달리 중복 계산이 없다. 또한 반복문을 사용하기 때문에 함수 호출이 발생 X
동전 거스름돈 구하기
-
1원,4원,6원 동전을 가지고 있는데 8원을 거슬러 줘야할 때 최소 몇개의 동전을 거슬러주면 될까?
-
그리디한 접근 : 6원, 1원, 1원
-
최적해 : 4원, 4원
그리디 방법이 항상 최적해를 구하는 것이 아님 -> DP로 접근해보자!!
상향식 접근
- C[n] = n원을 거슬러 줄 때의 최적
- 점화식 : C[n] = MIN(n-1 >=0 -> C[n-1]+1, n-4>=0 -> C[n-4] +1, n-6>=0 -> C[n-6]+1)
이항 계수 구하기
이항 정리
- 이항 다항식 x + y 의 거듭제곱 (x + y)2에 대해, 전개한 각 항 xky1-k의 계수 값을 구하는 정리
- 구체적으로 xky1-k의 계수는 n개에서 k개를 고르는 조합의 가짓수은 nCk이고 이를 이항계수라 한다.
동적 계획법을 적용한 이항계수 계산
bino(n, k)
B[][]
for i in 0 -> n
for j in 0 -> minimum(i, k)
if j=0 OR j=1
B[i][j] = 1
else
B[i][j] = B[i-1][j-1] + B[i-1][j]
return B[n][k]0/1 Knapsack
- 10kg 용량의 배낭에 4가지 선물 중 선택해서 넣을 수 있다하면 최대 가치가 되도록 선택하는 방법은?
- 5kg/10만원
- 4kg/40만원
- 6kg/30만원
- 3kg/50만원
- 배낭(Knapsack)문제는 n개의 물건과 각 물건 i의 무게 Wi와 가치 vi가 주어지고, 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배낭에 담은 물건의 무게의 합의 W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.
DP로 접근하기
-
배낭 문제의 부분 문제를 찾아내기 위해 조건을 살펴보면
- 물건, 물건의 무게, 물건의 가치, 배낭의 용량 총 4가지의 요소가 있다.
-
이 중에서 물건과 물건의 무게는 부분 문제를 정의하는데 반드시 필요
-
왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정하기 때문
-
또한 물건을 배낭에 담으려고 할 때 배낭 용량의 초과 여부를 검사해야 한다.
-
따라서 배낭문제의 부분 문제를 아래와 같이 정의 가능하다
- W = 배낭의 용량(kg)
- (vi, wi) = 가치(만원), 무게(kg) 물건
- K[i,w] = 물건 1 ~ i 까지 고려하고, (임시)배낭의 용량이 w일 때의 최대 가치
-
K[i,w]를 재귀로 표현하면
for i in 0 -> n : k[i, 0] = 0
for w in 0 -> w : k[0, w] = 0
for i in 1 - > n
for w in 1 -> w
if wi > w
K[i, w] = K[i-1, w]
else
K[i, w] = max(vi + K[i-1, w - wi], K[i-1, w])
return K[n, W]d
만반잘부