[SWEA] 동적 계획법(Dynamic Programming)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리했습니다

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYNNbK29EDFAVT# 

SW Expert Academy

동적 계획법(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)

재귀함수로 구현할 경우 구현하기는 쉬우나 엄청난 중복 호출이 존재한다는 문제점이 있음

n=7일 경우 f(2)를 7번이나 중복 호출함

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]

단점

1. 추가 메모리 공간 필요
2. n값이 커질 수록 실행 속도 저하, stack overflow 발생

2) 동적 계획법(Dynamic Programming: DP)

동적계획 알고리즘이란?

: 작은 부분에서 큰 부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 설계 기법

1. 최적화 문제 해결
   : 최대값 또는 최소 값을 구하는 문제
   : 여러개의 최적해 중 임의의 최적해 하나를 찾는 것
2. 완전 검색을 좀 더 효율적으로 하는 방법
3. 재귀(Recursive)와 메모이제이션(Memoization)을 결합한 것
   : 재귀-문제를 재귀적으로 정의해서 해결하는 것
4. 점화식을 찾으면 됨
   : 점화식을 찾으려면 문제를 분석하여 재귀적으로 정의하고 수식 형태로 표현

동적계획법의 적용 요건

1. 중복 부분문제 구조(Overlapping subproblems)
   : 순환적인 관계의 명시적 표현-점화식 사용
   : 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복사용
   : 메모이제이션을 사용
   : 이미 해결한 작은 문제의 해가 다시 필요할 때 테이블을 참조하여 중복 계산을 피함
2. 최적 부분문제 구조(Optimal substructure)
   : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함(Principle of Oprimality)
   : 최장 경로 문제의 경우 최적하의 원칙이 적용되지 않음

분할정복 vs 동적 계획법

분할 정복	동적 계획법
주어진 문제를 부분 문제들로 분할	부분문제들이 더 작은 부분문제들의 해를 공유
부분문제를 재귀적으로 해결, 필요 시 부분문제의 해를 결합	모든 부분문제를 한번만 계산, 결과 저장하여 필요 시 재사용

부분문제 사이의 의존적 관계

• 함축적인 순서(Implicit order) : 부분문제 사이의 의존적 관계는 문제에 따라 다르고 대부분 뚜렷이 보이지 않음

  분할 정복	동적 계획법
  하향식 방법	상향식 방법
  더 이상 나눌 수 없을때까지 쪼개서, 작은 문제의 해를 구하고 더 큰 문제를 해결	작은 문제의 해를 구하여 더 큰 문제의 해를 구함

동적 계획법 적용 방법

1. 최적해 구조의 특성 파악
   : 문제를 더 작은 부분 문제로 나누어 봄
2. 최적해 값의 재귀적 정의
   : 부분 문제들의 최적해를 사용하여 더 큰 문제의 최적해 값 정의
   : 점화식 사용 가능
3. 상향식 방법으로 최적해 값 계산
   : 의존성에 위배되지 않도록 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
4. 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구함

피보나치 수의 동적계획법 적용 알고리즘

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]

장점

1. 재귀 알고리즘 구현에 비해 수행속도 빠름
   : 중복 계산이 없고, 반복문 사용으로 함수 호출이 발생하지 않음

4차시. 동전 거스름돈 문제와 이항계수

**동적계획 알고리즘**: 작은 부분에서 큰 부분의 해들을 모두 구하여 최종적으로 원래 주어진 문제를 해결하는 설계 기법
- 동적 계획법 적용 조건

1. 중복 부분문제 구조 : 문제의 순환적 성질로 이전에 계산된 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복사용되는데, 메모이제이션을 사용하여 중복 계산을 피함
2. 최적 부분문제 구조 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 함
   - 분할정복 vs 동적 계획법
3. 분할 정복 : 주어진 문제를 부분 문제들로 분할하나 작은 문제의 해가 큰 문제의 해에 중복되어서 사용되지 않음(예: 퀵 정렬, 병합 정렬)
4. 동적 계획법 : 부분 문제들이 더 작은 부분문제들의 해를 공유

동전 거스름돈 문제와 이항계수

1. 동전 거스름돈 문제
   **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

2. 이항 계수 문제
   **이항 정리**
   : 이항 다항식 x+y 의 거듭제곱 n에 대해서 전개한 각 항 x^ky^(n-k)의 계수 값을 구하는 정리로 x^ky^(n-k)의 계수는 n개에서 k개를 고르는 조합의 가짓수인 nCk 즉 이항계수와 같다.

**이항 계수를 구하는 공식**

1. 일반 수식: nCk = n!/k!(n-k)!
2. 계산을 더 빠르게 하기위해 펙토리얼 계산을 뺸 수식: |n-1, k-1| + |n+1, k| if( 0 < k < n), 1 (if k = 0 || k = n)
   -> 두 번째 수식은 완전 검색에서 보았던 조합의 재귀적 정의와 같음!

**파스칼의 삼각형**
: 이항 계수를 삼각형 모양의 기하학적 형태로 배열한 것

1. C(n,0) = 1
2. C(n,n) = 1
3. C(n,k) = C(n-1,k-1) + C(n-1,k)

피보나치

1. 재귀호출 : O(2^n)
2. DP(메모이제이션) : O(n)
3. Dnc(matrix이용) : O(logn)

동전 거스름 돈 문제

1. 그리디
2. DP

이항 계수 문제

1. 재귀호출
2. DP(메모이제이션)

동적계획법의 적용

배낭문제(Kanpsack Problem)

물건 n개(각 물건에는 무게와 가치가 주어짐), 배낭의 용량 w 일 때, 배낭에 담을 수 있는 물건의 최대 가치는?
조건1. 배낭에 담은 물건의 무게의 합이 배낭의 용량 W를 초과할 수 없음
조건2. 물건은 할 개 씩만 있으며, 쪼개서 담을 수 없음

상태 공간 트리 탐색 방법

1. 깊이 우선 탐색 DFS(Backtracking) : O(2^n)
2. 너비 우선 탐색 BFS
3. 최고 우선 탐색 Best-First Search(A* algorithm)