[Python/코테] 다이나믹 프로그래밍(1) - 개념, 피보나치 수열 구현, 메모이제이션

다이나믹 프로그래밍

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

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 탑다운(하향식)과 보텀업(상향식) 방식으로 구현된다.

- 동적 계획법이라고도 부른다. 그러나 자료구조의 동적할당(프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법)의 '동적'의 뜻과는 달리 아무 의미가 없다.

 

사용 조건

1. 최적 부분 구조 (Optimal Substructure)

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제 (Overlapping Subproblem)

- 동일한 작은 문제를 반복적으로 해결해야 한다.

 

피보나치 수열

피보나치 수열을 점화식으로 표현하면 다음과 같다. 

프로그램에서는 이러한 수열을 배열이나 리스트를 이용해 표현한다.

점화식은 재귀함수를 통해 구현 가능하다. 파이썬으로 피보나치 수열을 구현한 예이다.

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

그러나 재귀함수로 구현하면 $O(2^N)$인 지수 시간 복잡도를 가지게 된다.

피보나치 수열은 다이나믹 프로그래밍의 사용 조건 두 가지를 만족하므로 사용 가능하다.

메모이제이션 Memoization

- 다이나믹 프로래밍의 탑다운(하향식) 구현법 중 하나 (dp에만 국한되는 개념은 아님. 더 넓은 개념)

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 별도의 변수에 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

* 다이나믹 프로그래밍의 전형적인 형태는 보텀업(상향식) 방식이다.

- 결과 저장용 리스트를 DP 테이블이라고 부른다.

# 탑다운 방식의 피보나치 수열 - 메모이제이션
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]

print(fibo(99))

# 보텀업 방식의 피보나치 수열
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])

분할 정복과의 비교

- 퀵정렬과 같은 문제를 분할 정복이라고 한다.

- DP와 공통점: 최적 부분 구조를 가질 때 사용. 작은 문제 답을 모아 큰 문제 해결.

- DP와 차이점: 부분 문제의 중복. 서로 영향을 미치는 동일한 부분 문제의 중복이 발생하는가?

다이나믹 프로그래밍 문제 접근법

- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다.

- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드는 개선하는 방법 사용