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

오늘은 동적 계획법(Dynamic Programming)에 대해 정리하려고 합니다.

그리디 알고리즘(Greedy Algorithm) 코딩 문제를 풀다가 그리디 알고리즘(Greedy Algorithm) 정리가 필요할 거 같아서

정리하던 도중 동적 계획법(Dynamic Programming)에 대해서도 정리하면 좋을 것 같아 정리하려 합니다.

 

동적 계획법은 '큰 문제를 작은 문제로 나누어 푸는 방법' 입니다.

동적 계획법은 분할 정복(Divide and Conquer)과 문제를 작은 단위로 분해한다는 비슷한 점이 있습니다.

(분할 정복은 문제를 나눌 수 없을 때까지 쪼갠 후 하나씩 처리하면서 결과를 합치는 알고리즘입니다.)

하지만 동적 계획법과 분할 정복의 가장 큰 차이점은 같은 연산을 중복하냐 안 하냐의 차이입니다.

 

분할 정복은 단순히 문제를 작은 단위로 나누고,

동적 계획법은 작은 문제들이 반복되어 처리될 수 있도록 하는 방법입니다.

 

동적 계획법을 구현할 때는 해결한 작은 문제는 다시 풀지 않습니다.

다른 곳에 저장해놓고 큰 문제를 해결할 때 필요한 작은 문제의 결괏값을 가져와 사용합니다.

 

Memoziation

Memoziation은 먼저 해결한 작은 문제를 이후 다시 사용할 수 있게 저장하는 것을 의미합니다.

 

피보나치수열

동적 계획법의 가장 대표적인 문제인 피보나치수열로 설명을 해보려 합니다.

피보나치수열은 0, 1, ,1 ,2, 3, 5, 8, 13,... 과 같이 0, 1을 제외한 수는 앞 두 수의 합인 수열입니다.

 

피보나치수열의 코드는 다음과 같습니다.

def fibo(n):
    fiboList=[1, 1]
    if n==1 or n==2:
        return 1
    for i in range(2,n):
        fiboList.append( fiboList[i-1] + fiboList[i-2] )
    return fiboList

n 번째 피보나치 수를 구할 때,

해당 n 번째 숫자가 나올 때까지, 이전 피보나치 숫자들을 계산하고 fiboList에 저장(Memoziation)하는 것을 볼 수 있습니다.

 

반복문이 돌아가면서 n번째 피보나치 수를 구하는 문제( 큰 문제 )를 해결하기 위해

이전 피보나치 숫자들이 같은 방식으로 반복해서 해결( 작은 문제 )됩니다.

 

그리고 중간중간 해결되는 작은 문제들은 어떤 N 번째 피보나치 숫자를 구하더라도

값이 항상 같다는 점도 확인할 수 있습니다.

 

동적 계획법으로 문제를 풀 때는  중복되는 작은 문제를 찾는 것이 가장 중요하다고 생각이 들었습니다.

작은 문제를 일반화하여 코드를 작성해놓으면 코드가 반복하면서 큰 문제까지 해결할 수 있습니다.

 

이상 피보나치수열 예제로 동적 계획법(Dynamic Programming)에 대해 알아보았습니다.