동적 계획법과 분할 정복

동적 계획법과 분할 정복

• 동적 계획법 (DP)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 부문 문제를 해결
  • 상향식 접근법으로, 상위 문제를 풀어가는 방식
  • Memoization : 프로그램 실행 시 이전에 계산한 값을 저장하여, 실행 속도를 빠르게 하는 기술
  • 문제를 쪼갤 때, 부분 문제는 중복되어, 재활용 된다. (피보나치)

• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 병합 정렬, 퀵 정렬

공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법은 중복되어, 상위 문제에 재활용
  • 분할 정복은 서로 중복되지 않는다.

동적 계획법 알고리즘

• 대표적인 알고리즘은 피보나치 (Dynamic Programing)

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

• recursive call 을 사용할 경우 계속 값을 계산해야 되기 때문에 비효율적이다. (동적 계획법 x)

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]

• memoization 기법을 통해 계산된 값을 이용해서 계산을 하기 때문에 효율적인 알고리즘이 만들어진다.