[코테 준비] 다이나믹 프로그래밍

다이나믹 프로그래밍

-> 메모리를 적절히 사용하여 수행 시간 효울성을 비약적으로 향상시키는 법
이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함, 다이나믹 프로그래밍의 구현은 일반적으로 2가지 방식(탑다운, 보텀업)으로 구성됨

-> 동적 계획법이라고도 불린다.
일반적인 프로그래밍에서는 동적(Dynamic)의 뜻은 '프로그래밍이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'
반면, 알고리증메서 사용하는 동적(Dynamic)은 특별한 의미x

다이나믹 프로그래밍의 조건

1. 최적 부분 구조 (Optimal Substructure)
   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   동일한 작은 문제가 반복적으로 호출되어 동일한 문제를 반복적으로 해결해야할 때

---

문제 예시 1. 피보나치 수열

다음과 같은 형태의 수열, 다이나믹 프로그래밍으로 효과적으로 계산 가능

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 

* 각각의 피보나치 수는 앞의 2개의 수의 합으로 이루어짐

• 점화식 : 인접한 항들 사이의 관계식
  
  

피보나치 수열 단순 재귀 소스코드 (python)

# 피보나치 함수를 재귀함수로 구현

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

print(fibo(4))

실행 결과

3

피보나치 수열의 시간 복잡도 분석
-> 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨
중복으로 호출되는 부분이 발생한다.

• 빅오표기법 : O(2의 N제곱)

---

다이나믹 프로그래밍 구현(탑다운) : 메모이제이션 (Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져 옴
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

-> 다이나믹 프로그래밍으로 문제를 풀 때, 사용하는 배열의 이름을
메모, 캐시, 테이블, dp, d 라고 설정한다.

탑다운 vs 보텀업

-> 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
결과 저장용 리스트는 DP 테이블이라고 부름

* 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 으미한다. 따라서, 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
한 번 계산된 결과를 별도의 공간에 담기만 한다면 캐시를 사용했다.
메모이제이션 기법을 사용했다고 말 할 수 있다.
메모이제이션과 다이나믹 프로그래밍은 서로 다른 개념이다.

---

피보나치 수열 탑다운 다이나믹 프로그래밍 소스 코드(python)

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

# 피보나치 함수를 재귀함수로 구현 (탑다운)
def fibo(X):
	# 종료 조건 (1 혹은 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))
       

피보나치 수열 보텀업 다이나믹 프로그래밍 소스 코드(python)

# 앞서 계산된 결과를 저장하기 위한 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])