[알고리즘] CH08 다이나믹 프로그래밍(DP, 동적계획법)

※ '이것이 코딩 테스트다 with 파이썬'을 참고하여 작성(요약)

 

다이나믹 프로그래밍(Dynamic Programming) = DP = 동적계획법

: 메모리 공간을 좀 더 사용해 연산 속도를 비약적으로 증가 시키는 방법

대표적 예) 피보나치 수열 : 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열(점화식 사용)

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

cf) 점화식 : 인접한 항들 사이의 관계식 의미

 

=> 이러한 수열을 배열이나 리스트로 표현 가능

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
	# 첫째항 이거나 두번째 항일 경우
	if x == 1 or x == 2:
   		return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4))

- 하지만 이런 식으로 재귀로 작성하면 n이 커질수록 수행 시간이 기하급수적으로 늘어남(O(2^n)의 지수시간 소요)

- 심지어 동일 함수가 반복적으로 호출됨(중복 문제)

 

피보나치 수열은 메모이제이션 기법 사용해 해결 가능

- f(1)을 구한 걸로 f(2)구하고 .. 이런 식이기 때문에 O(N)의 시간 복잡도 가짐

 

※ 메모이제이션 = 캐싱

: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류(DP보다 큰 개념), 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

- 때에 따라 사전 자료형 이용할 수 있음 => 이때는 수열처럼 연속적이지 않은 경우 유용(일부의 작은 문제에 대한 해답만 필요한 경우 존재)

 

DP 사용 위한 조건

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

1-1. 큰 문제를 작은 문제로 나눌 수 있다 : 최적 부분 구조

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

 

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

: 동일한 작은 문제를 반복적으로 해결해야 함

 

 

DP의 2가지 방식

1. Top-Down 방식 = 하향식

: 재귀함수 이용한 DP풀이, 큰 문제 해결 위해 작은 문제 호출

=> 만약, 탑다운 방식으로 문제를 풀려면 setrecursionlimit()함수를 통해 재귀 제한을 풀어주자

 

2. Bottom-Up 방식 = 상향식

: DP의 전형적 방식, 반복문 이용한 DP풀이, 작은 문제부터 큰 문제로 차근히 문제 해결

=> 스택의 크기가 한정되어 있기 때문에 보텀업 방식으로 문제 푸는 걸 권장

 

- 피보나치 수열 소스코드(재귀적 - 탑다운)

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100 # 총 100개(0~99까지)  => DP테이블

# 피보나치 함수를 재귀함수로 구현(탑 다운 DP)
def fibo(x):
	# 종료 조건(이거 대신 d[1] = 1, d[2] = 2이런 식으로 명시해도 됨) 
	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테이블 초기화(DP테이블은 메모이제이션을 위한 기록용)
d = [0] * 100

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

# 피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
# 첫 번째, 두 번째 피보나치 수는 이미 값이 있으므로 3부터 시작
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]
    
print(d[n])

 

 

 

문제 접근 법 - DP 유형임을 파악하기

=> 만약, 그리디, 구현, 완탐 등으로의 접근 시, 시간이 오래 걸린다면 DP로 적용 가능한지 확인(부분 문제들의 중복여부 확인)