동적 프로그래밍 방법론

이번 포스팅은 동적 프로그래밍 방법론입니다.

 

방법론의 이름을 들으면 "??? 대체 무슨 방법론이야?" 라는 생각이 듭니다.

 

이름을 그대로 해석하면 이해를 할수가 없습니다.

 

동적 프로그래밍 방법론은 동적 계획법이라고 불리며

 

국소해를 저장하는 Table을 구축하고, 국소해를 저장/사용하는 알고리즘 방법론을 의미합니다.

 

아래 피보나치 수열을 구하는 방법을 보겠습니다.

(너무 유명한 예제이지만, 이것만큼 숙련된 조교도 없습니다)

#분할정복 방법을 사용한 피보나치수열을 구하는 함수
def fib_div(n):
    if n == 1:
        return 1
    elif n == 0:
        return 0
    result = fib_div(n-1) + fib_div(n-2)
    return result

#동적 프로그래밍 방법을 사용한 피보나치수열을 구하는 함수
def fib_dy(n):
    #동적계획법에 사용되는 국소해를 저장하는 List
    temp_list = []
    temp_list.append(0)
    temp_list.append(1)
    for i in range(n):
        temp_list.append(temp_list[-1]+temp_list[-2])
    return temp_list[n]

코드를 보면, 명확한 차이를 느낄 수 있습니다.

 

1. 분할정복 방법론은 result를 구하기 위해서 큰 Data를 쪼개서 내려가지만

동적 프로그래밍 방법론은 작은 Data부터 시작해서 Result로 합쳐진다.

 

2. 동적 계획법은 이전의 국소해를 활용하기 위해서 국소해를 저장하는 List를 사용한다.

 

이만큼 확실하게 설명해주는 예제가 없습니다.

 

이때 동적계획법이 굳이 메모리를 추가로 할당하면서 국소해 list를 운용하는지 알아보겠습니다.

분할정복 방법론을 사용할 경우 F(4)를 구하기 위한 Tree

위 이미지는 분할정복 방법으로 피보나치수열의 4번째 값을 구하는 경우입니다.

 

보시면 F(4)를 구하기 위해서 F(2)가 2번 사용됩니다.

 

동적 프로그래밍 방법론에서는 F(2)의 국소해가 있는 list를 참조하면 됩니다.

 

하지만 분할정복 방법에서는 이전 국소해가 존재하지 않기 때문에 F(2)를 다시 계산해야합니다.

 

이게 만약 F(100000)을 구하는 문제라면? 동일한 작업이 비정상적으로 많아지게 됩니다.

 

때문에 분할정복 방법은 이전 국소해를 사용하지 않는 경우

 

동적 프로그래밍 방법론은 이전 국소해가 다음 국소해에 영향을 주는경우에 주로 사용합니다.

 

 

동적프로그래밍 방법론은 최적성의 원리를 따르는 문제에 적용합니다.

최적성의 원리란
“주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성된다”

정렬을 하는 알고리즘은 국소적인 정렬 결과가 전체 정렬과 일치하지 않습니다.

 

때문에 정렬 알고리즘 보다는 피보나치 수열, 연쇄 행렬 곱셈 등 최적해를 찾는 문제에 많이 활용됩니다.