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

정의

• 동적계획법: 한 번 계산한 결과는 Memoization(메모이제이션) 기법을 통해 다시 계산하지 않는다.
  • 전체 문제를 해결하기 위해 작은 단위의 문제를 해결하고, 해결한 작은 단위의 문제의 답을 통해 전체 문제를 해결한다.
  • 상향식 접근법 (최하위 해답-작은 단위의 문제-을 구하고 단계적으로 올라가서 최상위 문제-전체 문제-를 해결한다.)
• 분할정복
  • 문제를 나눌 수 없을 때 까지 나누어 잘게 나누어진 문제의 답을 합쳐 전체의 답을 얻는 알고리즘
  • 하향식 접근법 (상위의 답을 구하기 위해 아래로 내려가면서 하위의 답을 구하는 방ㅎ식)
  • 일반적으로 재귀적으로 구현
  • 퀵 정렬, 병합정렬

공통점과 차이점

• 공통점: 문제를 잘게 쪼갠다.
• 차이점
  • 동적 계획법은 부분 문제가 중복되지만 분할 정복은 중복되지 않는다.
  • 동적 계획법은 Memoization 기법을 사용하고 분할 정복은 사용하지 않는다.

동적 계획법의 예시: 피보나치 수열

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

if __name__ == "__main__":
    print(fibo_recursive(5))

재귀호출을 통한 피보나치 수열 구하기

위 코드는 재귀호출을 통해 구현한 피보나치 수열을 구하는 함수다. 재귀호출을 사용하여 피보나치 수열의 값을 구할 경우, 위의 그림과 같은 단계를 거쳐 해답을 구한다. 수가 커질수록 함수를 호출하는 횟수가 많아지고, 그에 따라 비용도 발생한다.

def fibo_dp(num):
    cache = [0 for i in range(num+1)]
    cache[0] = 0
    cache[1] = 1

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

if __name__ == "__main__":
    print(fibo_dp(5))

위 코드는 동적 계획법을 통해 피보나치 수열을 구하는 함수를 구현했다. 1) cache라는 배열으로 한 번 계산한 값을 기억했으며, (memoization 기법) 2) f(5)의 값을 구하기 위해 f(0), f(1), f(2) 등의 값을 여러 번 계산하지 않았다. 구하려는 값이 커져도, 그 숫자와 1:1로 비례하여 계산 횟수가 늘어나기 때문에 Recursive한 방법보다 비용효율적이다.

분할 정복의 예시: 퀵 정렬, 병합 정렬

퀵정렬 (Quick sort)

병합정렬 (Merge sort)