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

1. 정의

• 동적 계획법(DP라고 많이 부름)

  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 답을(해를) 활용해 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘

  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해 상위 문제를 풀어가는 방식 => 큰 문제를 작은 문제로 나누었을 때 작은 문제를 1번만 풀어서 저장(메모이제이션)해두고 상위 문제에 활용하기 위해 사용(계산 최소화)

  • Memoization 기법을 사용

    • Memoization(메모이제이션)이란 : 프로그램 실행시 이전 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용 됨.

    • ex) 피보나치 수열

• 분할 정복

  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

  • 하향식 접근법으로, 상위 해답을 구하기 위해 아래로 내려가면서 하위 해답을 구하는 방식

    • 일반적으로 재귀함수로 구현한다

  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음

    • ex) 병합 정렬, 퀵 정렬 등

2. 공통점과 차이점 

 

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

 

3. 동적 계획법 알고리즘 이해

 

연습 - 피보나치 수열

피보나치 수열 - 재귀 용법 활용

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

### 만약 fibo(4)를 호출한다면 ###

fibo(4) = fibo(3) + fibo(2)
fibo(3) = fibo(2) + fibo(1)
fibo(2) = fibo(1) + fibo(0)

### 프로세스 스택이 여러번 계속해서 추가됨 (중복 호출)

 

피보나치 수열 - 동적 계획법 활용

def fibo_dp(num):
    # Memoization기법 사용하기 위해 저장공간을 list comprehension 사용해서 만든다
    # list comprehension => 다른 Sequence로 부터 새로운 Sequence (Iterable Object)를 만들 수 있는 기능           # 사용 : [출력표현식 for 요소 in 입력Sequence [if 조건식]]
    cache = [ 0 for index in range(num + 1)] # 0 ~ num까지의 공간을 가지고 있는 배열이 만들어짐
    cache[0] = 0
    cache[1] = 1

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

만약 num의 값이 매우 크다면 재귀함수보다 속도가 빠르다 (동일한 문제에 대해서 계속 계산할 필요가 없으므로)