[알고리즘] 동적 계획법(Dynamic Programming, DP)

동적 계획법

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법으로  이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다

 

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 링크

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

사용되는 곳

최단 경로 문제, 행렬의 제곱 문제

왜냐하면 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다.

 

단점

가능한 모든 방법을 고려해야 한다 이렇기에 약간의 시간이 걸린다는 단점이 있다.

이러한 단점을 극복하기 위해 그리디 알고리즘이 등장했다.

 

 

정의

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

 

적용 방법

• Top-Down (재귀함수 사용) - 재귀 횟수 제한 오류가 걸릴 수도 있다.
• Bottom-Up (반복문 사용)

 

피보나치 수열문제를 예로 들어보자

 

패스트캠퍼스 알고리즘 / 기술면접 자료

링크 : https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

 

 

우선 동적계획법이 아닌 그냥 재귀함수로써 풀게 된다면 빨간색 X표시에 대한 연산이 다 이루어지기 때문에 시간복잡도가 동적계획법보다 증가하게 된다.

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

 

 

Top-Down (재귀함수 사용) (하향식)

• 하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어나가는 방법
• 위에서 부터 계산해 나가는 방식
• Memoization

cache = [0] * 11


def fibo_Top_down(x):
    if x <= 1:
        cache[x]=x
        return x
    if cache[x] == 0:
        cache[x] = fibo_Top_down(x - 1) + fibo_Top_down(x - 2)

    return cache[x]


print(fibo_Top_down(10))
# 55
print(cache)
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

 

 

Bottom-Up (반복문 사용) (상향식)

• 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용하여 큰 문제의 정답을 풀어나가는 방법
• 밑에서 부터 값을 계산
• Tabulation(도표, 표..)

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과 Tabluation으로 나누는데 내 개인적인 생각이지만 둘다 그냥 Memoization이다 라고 해도 될 것 같다. 왜냐하면 두개의 방식을 보면 모두 전에 계산한 값을 저장하여, 다시 계산하지 않도록 하도록하는 것이 Memoization이기 때문이다.