Algorithm) Dynamic programming

Dynamic programming(동적계획법)이란 ? 

 

메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법

-> 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 작성 !

 

대표적인 예시 : 피보나치 수열

- n 번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 

- 단, 1번째 피보나치 수 = 1,2 번째 피보나치 수 = 1

 

# 피보나치 함수 소스코드 
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

-> But, 피보나치 수열의 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 

바로 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문 !

 

다이나믹 프로그래밍을 사용해서 효율적으로 해결해보자 ! 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

 

 

✨ 메모이제이션 기법

 

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에

메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

( 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.)

 

어떻게 구현될 수 있을까? 한 번 구한 정보를 리스트에 저장하는 것

다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 떄는

이미 구한 정답을 그대로 리스트에서 가져오면 된다 !

 

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

# 피보나치 함수를 재귀함수로 구현 - 탑다운 다이나믹 프로그래밍
def fibo(x):
    # 종료 조건 (1 혹은 2 일떄 1을 반환)
    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]

print(fibo(99))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
d = [0] * 100

# 첫 번쨰 피보나치 수와 두 번쨰 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현 - 보텀업 다이나믹 프로그래밍 
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
    
print(d[n])

재귀 함수를 이용하여 다이나믹 프로그래밍 소스 코드를 작성하는 방법을

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 

탑다운 방식이라고 말한다.

 

반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터

차근차근 답을 도출한다고 하여 보텀업 방식이라고 한다.

 

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식 ! 

보텀업 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 부르며, 

메모이제이션은 탑다운 방식에 국한되어 사용되는 표현 ! 

 

 

---

코딩테스트에서 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제된다.

문제를 푸는 첫 단계는 당연 문제가 다이나믹 프로그래밍임을 파악하기! 

완전 탐색으로 오래 걸릴때, 부분 문제들의 중복 여부를 파악해보자 

 

앞서 다루었던 수열 예제처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을

적용해서 수정하는 것도 좋은 방법 !

 

가능하다면, 보텀업 방식으로 해보자 ! 

시스템 상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문

=> 만약 소스코드에서 recursion depth 관련 오류가 발생한다면, 

sys 라이브러리에 setrecursionlimit() 함수를 호출하여 

재귀제한을 완화할 수 있다는 점 정도만 기억하자 !!