이코테 2021 유튜브 강의를 보며 정리한 글입니다!
📌 영상 보러 가기!

다이나믹 프로그래밍?

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도리 메모리 영역에 저장하여 다시 계산하지 않는 것이 핵심!
• 일반적으로 탑다운(하향식)과 보텀업(상향식)으로 구성

문제가 다음의 조건을 만족할 때 다이나믹 프로그래밍 사용 가능

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

• 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제 해결 가능

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

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

메모이제이션 (Memoization)?

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

1. 피보나치 수열을 탑다운 다이나믹 프로그래밍으로 구현 (python)

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

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
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))

2. 피보나치 수열을 보텀업 다이나믹 프로그램으로 구현 (python)

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

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

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

print (d[n])

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence, LIS)

• 전형적인 다이나믹 프로그래밍 문제
• 하나의 수열 array = {4, 2, 5, 8, 4, 11, 15}이 있다고 할 때, 가장 긴 증가하는 부분 수열을 찾는 문제

D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
라고 할 때, 점화식은 다음과 같다.

모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

수열 array가 주어지고, 수열의 길이를 n이라고 할 때 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 다음과 같다

dp = [1] * n

for i in range(1, n):
	for j in range(0, i):
    	if array[j] < array[i]:
        	dp[i] = max(dp[i], dp[j] +1)
            
return max(dp)