동적계획법 소개

1. 피보나치 수

2. 수학적 귀납법과 비둘기 집의 원리

3. 메모이제이션과 동적계획법

 

1. 피보나치 수 

> 현재 항의 값은 전항과 전전항의 합이다.

> f(n+2) = f(n) + f(n+1)

  - 레오나르도 피보나치가 연구한 수열

 

0, 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열

> 0, 1, 1, 2, 3, 5, 8, 13

 

피보나치 수열의 n번째 값을 계산하는 함수 F의 정의

> F(0) = 0, F(1) = 1 초기값

> F(n) = F(n-1) + F(n-2), n >= 2

 

1) 재귀함수로 구현

def fibo(n):
    if n < 2: return n
    else : return fibo(n-1) + fibo(n-2)

n이 2미만일 경우, 즉 n이 0일 때는 0을 리턴하고, 1일 때는 1을 리턴한다. 이것이 기존에 설정했던 초기값이다. 그렇지않을 경우에는 이전의 두 항을 더한 값을 리턴한다.

 

 

2) 재귀 함수의 문제점

엄청난 중복 호출을 가진다.

 

피보나치의 7번째 항을 구하는 과정이다. 같은 항을 엄청나게 중복호출하여 중복된 연산을 반복한다.

 

• 피보나치 함수에서 중복 호출이 얼마나 있을까?
• 중복을 피하기 위해 어떤 방법을 사용할 수 있을까?

2. 수학적 귀납법과 비둘기 집의 원리

1) 수학적 귀납법

• 주어진 등식이 n=1일 때 성립함을 증명
• n일 때 성립한다고 가정한 후, n + 1일 때 성립함을 증명
• 도미노의 원리에 의해서 모든 n에 대해서 성립함이 증명된다.

1. 귀납 기본(Induction base) : n=1 또는 n=0에 대해 등식이 성립함을 증명한다.

2. 귀납 가정(Induction hypothesis) : 임의의 n에 대해 등식이 성립한다고 가정한다.

3. 귀납 단계(Induction step) : 등식이 n+1에 대해서도 성립함을 증명한다.

 

2) 수학적 귀납법으로 피보나치 수의 함수 호출 횟수 계산

• T(n)은 fibo(n)을 계산하기 위해 fibo() 함수를 호출하는 횟수
• T(n)은 재귀 호출 트리 상의 노드의 개수

T(0) = 1;
T(1) = 1;
T(n) = T(n-1) + T(n-2) + 1, n >= 2
    > 2 * T(n-2) # T(n-1) > T(n-2)
    > 2^2 * T(n-4)
    > 2^3 * T(n-6)
    ...
    > 2^(n/2) * T(0)
    > 2^(n/2)

n >= 2일 때는 n-1에서의 함수 호출횟수, n-2에서의 함수 호출 횟수, 최초 함수 호출 1번을 더한다. 그 다음 T(n-2)는 T(n-1)보다 작으므로 T(n-1) + T(n-2) + 1은 2 * T(n-2)보다 크다. 이것을 반복하면 2^(n/2) * T(0)보다 크므로 T(0) = 1이므로 T(n)은 2^(n/2)보다 크다.

 

정리하면, 재귀적 알고리즘으로 구성한 재귀 트리의 노드의 수를 T(n)이라 하면, n >= 2인 모든 n에 대하여 T(n) > 2^(n/2)이다.

 

1. 귀납 기본
T(2) = T(1) + T(0) + 1 = 3 > 2 = 2^(2/2)
T(3) = T(2) + T(1) + 1 = 5 > 2.83 '=' 2^(3/2)

2. 귀납 가정
2 <= m < n일 때, T(m) > 2^(m/2)이라 가정

3. 귀납 단계
T(n) = T(n-1) + T(n-2) + 1
    > 2^((n-1)/2) + 2^((n-2)/2) + 1
    > 2^((n-2)/2) + 2^((n-2)/2)
    = 2 * 2^((n/2)-1)
    > 2^(n/2)

 

3) 비둘기집의 원리

n+1개의 물건을 n개의 상자에 넣을 경우 어느 한 상자에는 두 개 이상의 물건이 들어있다.

 

1. 귀류법으로 증명

• n개의 비둘기 집과 n+1마리의 비둘기가 있다고 가정
• 각 비둘기 집에 한마리 이하의 비둘기만 있다면, 전체 비둘기는 많아야 n마리이다.
• 비둘기는 모두 n+1마리 이므로 모순발생
• 따라서 어느 비둘기 집에는 두마리 이상의 비둘기가 존재한다.

2. 예시

• 서울에는 머리카락의 수가 같은 사람이 최소한 두명 존재
• 13명이 있으면 생일이 같은 달인 사람이 반드시 존재

3. 피보나치 수열의 중복

이것으로 피보나치 수열의 호출횟수를 구해보자.

 

n번째 피보나치 수를 구하기 위해서 알아야 할 값

> fibo(0) ~ fibo(n-1)까지의 값을 알면 fibo(n)을 구할 수 있다.

> fibo()함수를 n번 호출하여 값을 구할 수 있다.

 

n번째 피보나치 수를 구하기 위해 재귀 호출로 작성된 fibo(n)함수 호출

> fibo() 함수를 2^(n/2)번 이상 호출

> 2^(n/2) > n 이므로 중복호출이 발생한다는 것을 알 수 있다.

 

3. 메모이제이션과 동적 계획법

동적 계획법의 핵심이 되는 기술로, 컴퓨터 프로그램 실행 시 이전에 계산한 값을 메모리에 저장해서 중복 계산을 방지하여 전체적인 실행속도를 빠르게 하는 기술

 

1) 메모이제이션의 활용

fibo(n)의 값을 계산하자마자 저장하면 실행시간을 O(n)으로 줄일 수 있다.

• memo 리스트를 할당하고, 모두 0으로 초기화한다.
• memo[0] = 0, memo[1] = 1로 초기화한다.

def fibo(n):
    if n >= 2 and memo[n] == 0:
    	memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

 

> 피보나치 함수의 메모이제이션

• 추가적인 메모리 공간이 필요하다
• 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고, 실행 속도 저하 또는 오버플로우 발생가능하다.

-> 재귀호출로 인해 문제가 발생하므로 재귀호출을 사용하지 않는 알고리즘을 사용해보자!

 

2) 동적계획 알고리즘

그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. 최적화 문제는 최적(최대값, 최소값 등)의 값을 구하는 문제이다. 여러개가 있을 수 있으므로 임의의 하나를 구하는 것이다. The를 구하는 것이 아닌, An을 구하는 것이다.

 

 

3) 동적계획법

• 완전검색을 효율적으로 만든 것.
• 재귀 + 메모이제이션
  • 여기서 재귀는 문제를 재귀적으로 정의해서 해결하는 것을 말한다.
• 점화식을 찾으면 가능하다.

4) DP 적용 문제의 조건

1. 중복 부분문제 구조(Overlapping subproblems)

큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제를 해결한다.

• 순환적인 관계(Recurrence relation)를 표현하기 위해 점화식을 사용한다.
• 순환적인 성질 때문에 이전에 계산한 작은 문제의 해가 더 큰 문제의 해를 구할 때 중복해서 사용한다.
• 동적 계획법에서는 이미 해결된 작은 문제들의 해를 어떤 저장공간(table)에 저장한다.
• 이미 해결된 문제의 해를 table을 참조해서 중복된 계산을 피한다.

2. 최적 부분문제 구조(Optimal substructure)

동적 계획법이 모든 최적화 문제에 적용되는 것이 아니다. 최적화의 원칙을 만족할 때만 DP를 효율적으로 적용가능하다.

 

최적화의 원칙 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

 

DP 자체가 큰 문제의 최적해를 작은 문제의 최적해를 이용해서 구하기 때문에 이것을 만족핮지 않는다면 그 문제는 DP를 적용할 수 없다.

 

DP를 적용 못하는 예) 최장경로 문제 

5) 분할정복과 DP의 차이점

 

4. 동적계획법 적용하기

1. 최적해 구조의 특성 파악하기

• 문제를 부분 문제로 나눈다.

2. 최적해의 값을 재귀적으로 정의하기

• 부분 문제의 최적해에 기반하여 문제의 최적해 값을 정의
• 이 과정에서 점화식이 사용될 수 있다.

3. 상향식 방법으로 최적해의 값을 계산하기

• 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.
• 테이블에 저장된 부분 문제의 해를 이용하여 상위 부분문제의 최적해를 구한다.(상향식 방법)

피보나치 수 DP 적용

1. 문제를 부분 문제로 분할

2. 점화식으로 정의

3. 가장 작은 부분 문제부터 해를 구한다.

• 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

def fibo_dp(n):
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
    	f[i] = f[i-1] + f[i-2]
    return f[n]

 

• 재귀 알고리즘 보다 수행속도가 더 빠르다.
• 반복문을 사용하기 때문에 함수 호출이 발생하지 않는다.