[SWEA] 동적 계획법(Dynamic Programming)
본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리했습니다
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
동적 계획법(Dynamic Programming, 다이나믹 프로그래밍)
목차
01 피보나치 수
02 수학적 귀납법과 비둘기 집의 원리
03 메모이제이션과 동적 계획법
04 동전 거스름돈 문제와 이항 계수 문제
01 피보나치 수
피보나치 수(Fibobacci Number)란?
0과 1로 시작하고 이전의 두 수의 합을 다음 항으로 하는 수열
- 0, 1, 1, 2, 3, 5, 8 ...
피보나치 수열의 n번 째 값을 계산하는 함수 F의 정의
- $F_0 = 0, F_1 = 1$ (기본이 되는 경우)
- $F_n = F_{n-1} + F_{n-2} \ for \ n >= 2$ (유도된 경우)
함수 F의 정의로부터 피보나치 수열의 n번째 항을 반환하는 함수를 재귀함수로 구현
재귀적 정의와 알고리즘
$f(n) = f(n-1) + f(n-2) ( n >= 2, f(0) = 0, f(1) = 1)$
def fibo(n):
if n < 2 :
return n
else :
return fibo(n-1) + fibo(n-2)재귀함수로 구현할 경우 구현하기는 쉬우나 엄청난 중복 호출이 존재한다는 문제점이 있음
02 수학적 귀납법과 비둘기 집
수학적 귀납법(Mathematical induction)이란?
피보나치 함수의 중복 호출이 얼마나 있는지 알기 위해 이용하는 방법으로 시간복잡도 계산에 사용된다
- 귀납 기본(Induction base): 주어진 등식이 n = 1일 때 성립합을 증명
- 귀납 가정(Induction hypothesis): n일 때 성립한다고 가정
- 귀납 단계(Induction step): n+1일 때 성립함을 증명
- 모든 n에 대하여 성립
수학적 귀납법을 이용한 증명 과정
$T(0) = 1, T(1) = 1$
$T(n) = T(n-1) + T(n-2) + 1 > 2T(n-2) > 2{^2T(n-4)} > \cdots > 2^{\frac{n}{2T(0)}} = 2^{\frac{n}{2}}$
재귀적 알고리즘으로 구성한 재귀 트리의 노드의 수 T(n) -> T(n) = 2^{\frac{n}{2T(0)}} -> 시간복잡도 = $O(2^n)$
비둘기 집의 원리린?
비둘기 n+1 마리, 비둘기 집 n개가 있을 때 적어도 어느 한 집에는 두 마리의 비둘기가 있음을 증명하시오
귀류법을 통한 증명
비둘기 n+1 마리, 비둘기 집 n개가 있다고 하자.
만약 각 비둘기 집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기 집에는 많아야 n마리의 비둘기가 존대한다
이 경우 앞서 가정과 모순되므로 적어도 한 개의 비둘기 집에는 두 마리 이상의 비둘기가 있다
비둘기 집의 원리를 이용한 피보나치 수열의 중복 증명
- n번째의 피보나치 수를 구하기 위해 알아야 할 값 : fibo(0)~fibo(n-1)까지의 값을 fibo()함수를 n번 호출하여 값을 알면 됨
- n번째 피보나치 수를 구하기 위해 재귀 호출로 작성된 fibo(n)함수 호출 : fibo()함수 2^n/2 이상 호출 -> 2^n/2 > n
- 결론: 비둘기 집의 원리를 적용하면 중복해서 호출하고 있음을 알 수 있음 -> 시간복잡도는 n이 커질수록 2^n에 비례하여 증가
3차시. 메모이제이션과 동적계획법
1) 메모이제이션(memoization : to put in memory)
: 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
동적 계획법을 적용하기 위해 사용되는 핵심 기술
메모이제이션을 적용한 피보나치 알고리즘
: 피보나치 수를 구하는 알고리즘에서 입력 값 n에 대한 계산 결과 저장 -> 실행시간을 O(n)으로 줄일 수 있음
//memo 배열을 할당하고 모두 0으로 초기화
//단, memo[0] = 0 , memo[1] = 1로 초기화 한다(f(0) = 0, f(1) = 1)
fibo(n)
if n >= 2 and memo[n] = 0:
memo[n] <- fibo1(n-1) + fibo(n-2)
return memo[n]단점
- 추가 메모리 공간 필요
- n값이 커질 수록 실행 속도 저하, stack overflow 발생
2) 동적 계획법(Dynamic Programming: DP)
동적계획 알고리즘이란?
: 작은 부분에서 큰 부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 설계 기법
- 최적화 문제 해결
: 최대값 또는 최소 값을 구하는 문제
: 여러개의 최적해 중 임의의 최적해 하나를 찾는 것 - 완전 검색을 좀 더 효율적으로 하는 방법
- 재귀(Recursive)와 메모이제이션(Memoization)을 결합한 것
: 재귀-문제를 재귀적으로 정의해서 해결하는 것 - 점화식을 찾으면 됨
: 점화식을 찾으려면 문제를 분석하여 재귀적으로 정의하고 수식 형태로 표현
동적계획법의 적용 요건
- 중복 부분문제 구조(Overlapping subproblems)
: 순환적인 관계의 명시적 표현-점화식 사용
: 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복사용
: 메모이제이션을 사용
: 이미 해결한 작은 문제의 해가 다시 필요할 때 테이블을 참조하여 중복 계산을 피함 - 최적 부분문제 구조(Optimal substructure)
: 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함(Principle of Oprimality)
: 최장 경로 문제의 경우 최적하의 원칙이 적용되지 않음
분할정복 vs 동적 계획법
| 분할 정복 | 동적 계획법 |
|---|---|
| 주어진 문제를 부분 문제들로 분할 | 부분문제들이 더 작은 부분문제들의 해를 공유 |
| 부분문제를 재귀적으로 해결, 필요 시 부분문제의 해를 결합 | 모든 부분문제를 한번만 계산, 결과 저장하여 필요 시 재사용 |
부분문제 사이의 의존적 관계
- 함축적인 순서(Implicit order) : 부분문제 사이의 의존적 관계는 문제에 따라 다르고 대부분 뚜렷이 보이지 않음
분할 정복 동적 계획법 하향식 방법 상향식 방법 더 이상 나눌 수 없을때까지 쪼개서, 작은 문제의 해를 구하고 더 큰 문제를 해결 작은 문제의 해를 구하여 더 큰 문제의 해를 구함
동적 계획법 적용 방법
- 최적해 구조의 특성 파악
: 문제를 더 작은 부분 문제로 나누어 봄 - 최적해 값의 재귀적 정의
: 부분 문제들의 최적해를 사용하여 더 큰 문제의 최적해 값 정의
: 점화식 사용 가능 - 상향식 방법으로 최적해 값 계산
: 의존성에 위배되지 않도록 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장 - 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구함
피보나치 수의 동적계획법 적용 알고리즘
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]장점
- 재귀 알고리즘 구현에 비해 수행속도 빠름
: 중복 계산이 없고, 반복문 사용으로 함수 호출이 발생하지 않음
4차시. 동전 거스름돈 문제와 이항계수
**동적계획 알고리즘**: 작은 부분에서 큰 부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 설계 기법
- 동적 계획법 적용 조건
- 중복 부분문제 구조 : 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복사용되는데, 메모이제이션을 사용하여 중복 계산을 피함
- 최적 부분문제 구조 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함
- 분할정복 vs 동적 계획법 - 분할 정복 : 주어진 문제를 부분 문제들로 분할하나 작은 문제의 해가 큰 문제의 해에 중복되어서 사용되지 않음(예: 퀵 정렬, 병합 정렬)
- 동적 계획법 : 부분 문제들이 더 작은 부분문제들의 해를 공유
동전 거스름돈 문제와 이항계수
- 동전 거스름돈 문제
**Q.사용할 수 있는 동전 1,4,6원 일때 거스름돈 8원에 대한 최소 동전 개수는 몇 개 일까?**
- 그리디 방법의 접근: 6,1,1원
- 최적해: 4,4 원
(결론): 그리디 방법으로 동전 거스름돈의 최적해를 구할 수 없는 경우가 있다
구현 방법
**재귀 알고리즘에 메모이제이션 적용**
: 상태 공간 트리를 사용하여 단말노드 방문 시 중복되는 부부은 메모이제이션을 통해 최소화
**동적 계획법 : 상향식**
- 1원에 대한 최적해 -> 2원에 대한 최적해 -> ... -> 8원에 대한 최적해
f(n) = min(f(n-6),f(n-4),f(n-1)} + 1
- 이항 계수 문제
**이항 정리**
: 이항 다항식 x+y 의 거듭제곱 n에 대해서 전개한 각 항 x^ky^(n-k)의 계수 값을 구하는 정리로 x^ky^(n-k)의 계수는 n개에서 k개를 고르는 조합의 가짓수인 nCk 즉 이항계수와 같다.
**이항 계수를 구하는 공식**
- 일반 수식: nCk = n!/k!(n-k)!
- 계산을 더 빠르게 하기위해 펙토리얼 계산을 뺸 수식: |n-1, k-1| + |n+1, k| if( 0 < k < n), 1 (if k = 0 || k = n)
-> 두 번째 수식은 완전 검색에서 보았던 조합의 재귀적 정의와 같음!
**파스칼의 삼각형**
: 이항 계수를 삼각형 모양의 기하학적 형태로 배열한 것
- C(n,0) = 1
- C(n,n) = 1
- C(n,k) = C(n-1,k-1) + C(n-1,k)
피보나치
- 재귀호출 : O(2^n)
- DP(메모이제이션) : O(n)
- Dnc(matrix이용) : O(logn)
동전 거스름 돈 문제
- 그리디
- DP
이항 계수 문제
- 재귀호출
- DP(메모이제이션)
동적계획법의 적용
배낭문제(Kanpsack Problem)
물건 n개(각 물건에는 무게와 가치가 주어짐), 배낭의 용량 w 일 때, 배낭에 담을 수 있는 물건의 최대 가치는?
조건1. 배낭에 담은 물건의 무게의 합이 배낭의 용량 W를 초과할 수 없음
조건2. 물건은 할 개 씩만 있으며, 쪼개서 담을 수 없음
상태 공간 트리 탐색 방법
- 깊이 우선 탐색 DFS(Backtracking) : O(2^n)
- 너비 우선 탐색 BFS
- 최고 우선 탐색 Best-First Search(A* algorithm)