[Python][이코테] 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍

Dynamic Programming

 

모든 프로그램은 컴퓨터의 연산 속도와 한정된 메모리 공간에 제한되어 있다.

 

다이나믹 프로그래밍은 이러한 제한 속에서 우리는 주어진 요소들을 최대한으로 활용하는 효율적인 알고리즘을 작성해야 한다.

 

다이나믹 프로그래밍은 동적 프로그래밍, 동적 계획법 이라고도 한다.

---

피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로 피보나치 수열이 있다.

 

피보나치 수열을 우리가 학창 시절 배운 점화식을 이용해 풀어보면

 

$$a_{n+2} = f(a_{n+1}, a_{n}) = a_{n+1} + a_{n}$$
$$a_{n} = a_{n-1} + a_{n-2}, a_{1} =1, a_{2} = 1 $$

피보나치는 첫 번째 항과 두 번째 항이 1이기 때문에 위와 같이 정의된다.

 

즉

• n번째 피보나치 수 = (n - 1)번째 수 + (n - 2)번째 수
• 단, 1번째와 2번째 수는 1

이를 코드로 구현하면

 

# 8-1 DP 피보나치 수열
def fibo(x):
    if x == 1 or x==2:
        return 1
    return fibo(x-1) + fibo(x-2)
print(fibo(4)) # 3

하지만 위의 코드는 n이 커질수록 수행 시간이 기하급수적으로 증가한다.

 

위의 코드의 시간복잡도는 약 $O(2^n)$ 시간이 소요된다.

 

만약 n이 30이면 10억회 가량의 연산을 수행한다.

 

위의 제한적인 문제는 다이나믹 프로그래밍을 활용하여 효율적으로 해결할 수 있다.

 

다이나믹 프로그래밍은 다음과 같은 상황에서 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 위의 두 조건을 만족하는 대표 문제이다. 이 문제는 메모이제이션(Memoization) 기법을 사용한다.

 

메모이제이션(Memoization)은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.

 

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

 

구현 방법으로는 한 번 구한 정보를 리스트에 저장하는 것이다. 재귀적으로 수행하다가 같은 정보가 필요하면 이미 구한 정답을 리스트에서 꺼내오면 되는 것이다.

 

# 8-2 DP 피보나치 수열(재귀적)
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(top-down Dynamic Programming)
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]

print(fibo(99)) # 218922995834555169026

위의 코드를 실행하면 피보나치 연산을 99번 수행하지만 결과가 금방 출력된다.

 

---

정리하자면 다이나믹 프로그래밍은

 

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

비슷한 예로 퀵 정렬이 있다.

2022.09.13 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] 퀵 정렬

[Python][이코테] 퀵 정렬

 

퀵 정렬은 정렬을 수행할 때 정렬할 리스트를 분할하여 전체적으로 정렬이 될 수 있도록 한다.

 

이러한 방법을 분할 정복(Devide and Conquer) 알고리즘이라 한다.

 

DP와 분할 정복의 차이는 DP는 문제들이 서로 영향을 미치고 있다는 점이다.

 

퀵정렬

•  한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 더 이상 바뀌지 않고 해당 피벗 값을 다시 처리하는 부분 문제는 존재하지 않음

DP

• 한 번 해결했던 문제를 다시 해결함

예를 들어 재귀 함수를 사용하는 방법(메모이제이션)에서는 한 번 푼 문제는 그 결과값을 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다.

 

f(6) 일 경우 메모이제이션 기법을 이용하여 그려보면 아래 그림의 색칠된 노드만 방문하게 된다.

출처: 한빛미디어

다이나믹 프로그래밍을 이용한 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이 된다.

 

f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)의 값을 푸는데 사용되기 때문이다.

 

실제로 호출되는 함수에 대해서만 확인해보면 다음과 같다.

 

이를 코드로 확인해 보면

 

# 8-3 DP 호출되는 함수 확인

d = [0] * 100

def pibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = pibo(x - 1) + pibo(x - 2)
    return d[x]
pibo(6)
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

이처럼 재귀 함수를 이용해 DP를 사용하는 방법을

 

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 Top-Down 방식이라고 한다.

 

반대로 반복문을 이용하는 경우

 

작은 문제부터 답을 도출하여 Bottom-Up 방식이라 한다.

 

피보나치를 Bottom-Up 방식을 이용하면 아래의 코드와 같다.

 

# 8-4 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]
    
print(d[n]) # 218922995834555169026

---

Top-Down(메모이제이션) 은 '하향식'

Bottom-Up 은 '상향식'

 

DP의 전형적인 방식은 Bottom-Up 방식이다.

 

상향식에서 사용되는 결과 저장용 리스트는 'DP 테이블' 이라 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

 

메모이제이션은 때에 따라서 사전(dict)로 사용할 수도 있다.

 

사전 자료형은 수열처럼 연속적이지 않은 경우에 사용할 수 있다.

 

---

코딩 테스트 문제를 풀 때 DP문제일 경우 가장 중요한 것은

 

'DP 유형인지 아는 것'이다.

 

특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 DP를 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부를 확인하자.

 

또한 문제를 풀 때 재귀를 사용하는 Top-Down 보다는 반복문을 사용하는 Bottom-Up을 권장한다.

 

시스템상 재귀 함수의 스택 크기가 한정되어있을 수 있기 때문이다. 예를 들어 5천 번 이상 재귀를 실행하면 재귀 함수 깊이(recursion depth) 오류가 발생할 수 있다.

 

이러한 경우 sys 라이브러리에 포함된 serrecursionlimit() 함수를 사용하여 재귀를 완화할 수 있지만 Bottom-Up방식을 더 추천한다.