[알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

오늘은 다이나믹 프로그래밍(Dynamic Programming)에 대해서 알아보도록 하겠습니다. 

이름이 너무 무섭게 생겼기 때문에, 마음의 준비를 하고 알고리즘 공부를 시작했는데요, 

기초 이론은 생각보다 빡세지 않았고, '이게 다인가?' 하는 물음에 대해서 나무위키에서 시원하게 답이 나와있어서 좋았습니다 :)  

1. 다이나믹 프로그래밍(Dynamic Programming)이란? 

<파이썬 알고리즘 리뷰>

: 다이나믹 프로그래밍 알고리즘은 응용 수학자 리차드 벨만(Richard Bellman)이 1953년에 고안한 알고리즘으로, 리차드

벨만은 그전에 최단 거리를 구할때 사용하는 벨만-포드(Bellman-Ford)알고리즘을 고안하고, 머신러닝 분야의 '차원의 저주(Curse of Dimensionality)라는 이론을 만든 저명한 수학자입니다.

: 다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해두었다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다. 

: 대표적으로 병합 정렬과 퀵 정렬 등이 있으며, 이들은 모두 분할 정복 알고리즘으로 분류합니다. 

 

<나무위키>

: 조금 장난스럽게 말해서 '삽질을 하지 않기 위해 답을 재활용', 즉 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다고 합니다.
: 다른 말로는 "동적 계획법"이라고 하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없어서, 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을  '기억하며 풀기'로 더욱 적절하게 번역하였다고 합니다.

 

 

2. [대표 예시] '피보나치 수열'

1) 피보나치 수란?

: 수학에서, 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

: 위의 정의를 그대로 반영하여 점화식으로 표현된것을 볼 수있다. 

2) 피보나치 수열 코드

① 기본 코드

def fibo(x):
    if x == 1 or x ==2:
        return 1
    return fibo(x-1) + fibo(x-2)

: 피보나치수열의 기본 코드는 이렇게 간단하지만, n이 커지면 심각한 문제가 발생합니다. 이 소스코드의 시간복잡도는 엄밀히 말하면 세타표기법을 사용해서 θ(1.618^n)로 표현할 수 있으며 빅오 표기법으로는 O(2^n)의 지수시간이 소요됩니다. 예를들어 n이 30이라면, 약 10억 가량의 연산을 수행해야합니다. 

 

: 하지만, 피보나치 수열은 중복되는 계산이 반복됩니다. 예를들어 fibo(6)을 호출해본다고 합시다. 

: 위의 그림에서 14번의 fibo함수가 호출이되지만, 그중에 값이 1인 f(1), f(2)와 중복된것을 제외하면 위의 검은색 영역을 표시한 4개의 fibo값만 필요함을 알 수있습니다.

: f(n)에서 n이 커질수록 이렇게 중복으로 호출되는 값이 많아집니다. 너무나 비효율적입니다! 이러한 문제는 다이나믹 프로그래밍을 사용하여 효율적으로 해결할 수 있습니다.  

 

② 탑다운(Top-down) 방식

- '메모이제이션(Memozation)기법'

: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 가져오는 기법을 의미한다. 메모제이션은 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다.

# 한 번 계산된 결과를 메모이제이션하기위한 리스트 초기화
d = [0]*100

#피보나치 함수를 재귀함수로 구현(탑다운)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    #이미 계산한적 있다면 그대로 반환
    if d[x] != 0:
        return d[x]
    
    #아직 계산 안했다면, 점화식으로 가기
    d[x] = fibo(x-1) + fibo(x-2)
    
    return d[x]

: 여기서 기본 코드에서 추가된 것은 딱 한부분입니다. 해당 숫자의 함수값을 이미 계산했는가 안했는가를 d[x]라는 리스트를 두고 확인하여 그 여부에따라 계산했으면 기존 결과값을 아니면 새로운 계산을 진행합니다.

: 결론적으로 f(6)의 경우 필요한 14개의 함수 값 중에서 4개만 계산하여 값을 출력합니다. 

: 이와같이 다이나믹 프로그래밍은 큰 문제를 작게 나누고 같은 문제라면 한번씩만 풀어서 문제를 효율적으로 해결하느 알고리즘 기법입니다. 큰 문제를 작게 나누는 것은 앞서 공부했던 '퀵 정렬'에서 확인하실 수 있습니다.

: 퀵 정렬에서는 리스트를 분할하면서 정렬을 진행해 최종적으로는 전체 정렬이 될 수있도록 하는 알고리즘으로, 분할 정복(Divide and Conquer) 알고리즘으로 분류됩니다. 

 

 

 

③ 바텀업(Bottom-Up)방식

: 앞에서 탑다운 방식은 큰문제를 해결하기 위해 작은 문제를 호출하였으나, 반대로 작은 문제부터 차근차근 답을 도출하는 바텀업 방식도 있습니다.

# 한 번 계산된 결과를 DP 테이블 초기화
d = [0]*100

d[1] = 1
d[2] = 1
n =99

for i in range(3, n+1):
    d[i] = d[i-1]+d[i-2]

: 바텀업 방식에서는 재귀함수를 사용하지 않고, for 반복문으로만 문제를 해결합니다. 

: 바텀업 방식에서는 메모제이션이라는 단어를 쓰지 않고, 'DP 테이블'이라는 말을 사용합니다. (※ 메모제이션은 탑다운 방식에서만 국한되어 사용되는 표현이라고 합니다!)

 

3. 정리

- 탑다운(메모제이션) 방식은 '하향식'이라고 하며, 바텀업은 '상향식'이라고 합니다. 하지만, 이중에서 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이라고 하네요!

- 이전에 계산한 값을 저장하는 메모이제이션과 DP테이블의 자료형으로 리스트를 사용하였는데요, 경우에 따라서, 특히 연속적이지 않은 값이 필요한 경우에는 사전 자료형으로 저장하는것이 더 효율적입니다! 

 

<참고> '이것이 코딩 테스트다 with 파이썬'

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고