6. 다이나믹 프로그래밍

1. 다이나믹 프로그래밍 (동적 계획법)

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

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역(보통 DP 테이블이라 부름)에 저장하여 다시 계산하지 X

• 다이나믹 프로그래밍을 사용할 수 있는 조건

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

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

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

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

• 시간 복잡도

  • O(N)
    

• 다이나믹 프로그래밍 구현 방식

  1. 탑다운(Top-down) - 하향식 - 재귀함수 - 메모이제이션(Memoization)

     • 한 번 계산한 결과는 메모리 공간에 메모 -> 같은 문제를 다시 호출하면 메모했던 결과 그대로 가져옴

       • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

  2. 보텀업(Bottom-up) - 상향식 - 반복문

2. 피보나치 수열

🎨 1. 단순 재귀 소스코드

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

print(fibo(5)) # 5

• 시간 복잡도

  • O(2N) : 지수 시간 복잡도

  • 중복되는 부분 문제 발생

🎨 2. 탑다운 - 재귀함수 - 메모이제이션

d = [0] * 100

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

  # 이미 계산했던 적이 있는 문제라면 dp 테이블에서 가져옴
  if d[x] != 0:
    return d[x]
  
  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

print(fibo(99)) # 218922995834555169026

🎨 3. 보텀업 - 반복문

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

3. 다이나믹 프로그래밍 vs 분할 정복

	다이나믹 프로그래밍	분할 정복
최적 부분 구조	O	O
중복되는 부분 문제	O	X

• 분할 정복에서는 같은 부분 문제가 반복적으로 계산되지 않음

  • e.g., 퀵 정렬: 한 번 피벗으로 선정되어 분할 작업이 이루어진 데이터는 다시 피벗으로 선정될 일 X

[참고] 4. LIS

• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence): 수열이 주어졌을 때 증가하는 부분 수열 중 가장 긴 수열 찾기

  • e.g., array = {3, 2, 5, 8, 4, 11, 15} -> {2, 5, 8, 11, 15}

• 대표적인 다이나믹 프로그래밍 문제

🎨 [구하는 방법]

d[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

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

🎨 [소스코드]

n = int(input()) # 수열의 크기
array = list(map(int,input().split())) # 수열

d = [1] * n
'''
1로 초기화하는 이유는, d[i]가 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이기 때문에, 
자기 자신만 포함된 수열의 길이 1이 최솟값이기 때문
'''

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

print(max(d))
'''
여기서 만약 print(d[n-1])이라고 하면 마지막 수를 무조건 포함하는 최대 부분 수열 길이가 출력됨. 
그러나, 마지막 수를 포함하지 않는 수열이 최대 부분 수열이 될 수 있음. 
따라서 max()를 사용하여 dp 테이블에 저장된 길이들 중 최댓값을 찾아야 함.
'''

🎨 [실행 결과]

7
3 2 5 8 4 11 15
5

---

먼저 그리디, 완전 탐색 등의 아이디어로 문제의 해결이 가능한지 생각해보고, 다른 알고리즘으로 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍으로 접근해 보자.

다이나믹 프로그래밍 문제는 DP 테이블을 만들어 값을 메모해야 하기 때문에 살펴봐야 하는 값의 범위가 크지 않은 문제들이 대부분이었다. 역으로 생각하면, 고려해야 하는 값의 범위가 다른 문제들에 비해 현저히 작다면 다이나믹 프로그래밍 문제가 아닐까 생각해 보자!

다이나믹 프로그래밍 문제를 풀 때는 트리 그려보기! 점화식 세우기!

---

[참고]

• (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 (https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6)