5. 알고리즘 동적계획법(dynamic programming)과 분할정복

dynamic programming

동적계획법(Dynamic Programming)과 분할정복(Divide and Conquer)

1. 정의

• 동적계획법(DP라고 많이 부른다.)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결하고, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다.
  • Memoization 기법을 사용한다
    • Memoization이란? 프로그램 실행 시 이전에 계산한 값을 저장하며, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용 된다
    • 예 : 피보나치 수열
• 분할정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현한다.
  • 문제를 잘게 쪼갤 때, 부분문제는 서로 중복되지 않는다.
    • 예 : 병합 정렬, 퀵 정렬 등

2. 공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서 가장 작은 단위로 분할한다.
• 차이점
  • 동적계획법
    • 부분 문제는 중복되어, 상위 문제 해결시 재활용 된다. 
    • Memoization 기법을 사용한다. (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용한다)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않는다. 
    • Memoization 기법을 사용하지 않는다. 

3. 동적계획법(dynamic programming) 알고리즘

• 피보나치 수열
  • f(0)=0
  • f(1)=1
  • f(n)=f(n-1)+f(n-2) (n>1)
• f(3) :  f(2)와 f(1)을 풀어야하고 f(2)를 풀려면 f(1)과 f(0)을 풀어야 한다. 
• f(4) :  f(3)과 f(2)를 풀어야 하고 f(3)을 풀려면 f(2)와 f(1)을 풀어야하고 f(2)를 풀려면 f(1)과 f(0)을 풀어야 한다. 
• 위와 같이 부분 문제는 중복된다. 따라서 결과값들은 Memoization기법으로 저장해 놓는다. 

먼저, 재귀호출로 푸는 방법

def fibo(num) : 
    if num <= 1 : 
        return num
    return fibo(num-1) + fibo(num-2)

fibo(4)

3

 

아래는 피보나치 수열을 만족하는 것을 보여준다.

fibo(3) + fibo(2)

3

 

fibo(2)+fibo(1)+fibo(1)+fibo(0)

3

 

fibo(1)+fibo(0)+fibo(1)+fibo(1)+fibo(0)

3

이를 동적계획법(dynamic programming)을 이용하여 풀면 다음과 같다.

def fibo_dp(num) : 
    cache = [0 for index in range(num+1)]
    cache[0]=0
    cache[1]=1
    
    for index in range(2,num+1) : 
        cache[index] = cache[index -1] + cache[index -2]
    return cache[num]

cache 리스트에 미리 최하위 해답부터 저장해 놓은 후에 최상위 결과값을 구한다.

fibo_dp(10)

55

다시 동적계획법의 정의를 살펴보면 이해가 더 잘된다.

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결하고, 최종적으로 전체 문제를 해결하는 알고리즘이다.
• 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다.
• Memoization 기법을 사용하여 프로그램 실행 시 이전에 계산한 값을 저장하며, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 한다.

분할정복은 고급 정렬 알고리즘인 퀵 정렬, 병합정렬에서 사용되는 알고리즘이라서 다음챕터에서 다룬다.