다이나믹 프로그래밍

Dynamic Programming (=동적 계획법)

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방법. 시간 효율성을 비약적으로 향상시킨다.

• 자료구조에서 dynamic 이란?
  : 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법
  (그러나 여기서는 별다른 의미 없이 사용됨)

• 언제 사용 가능한가요?
  1. 최적 부분 구조
  : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음. → 어떤 문제에 대한 해가 최적일 때, 그 해를 구성하는 부분 문제들의 해 역시 최적이다.
  2. 중복되는 부분 문제
  : 동일한 작은 문제를 반복적으로 해결해야 할 때

피보나치 수열

점화식 : $a_n=a_{n-1}+a_{n-2}\quad a_1=1,\; a_2=1$

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

→ fibo(6)의 계산 과정을 그래프화 함.

• 시간 복잡도 : $O(N^2)$
  • f(2)가 여러 번 호출되어 시간이 낭비됨.

메모이제이션 (Memoization)

: 한 번 계산한 결과를 메모리 공간에 메모하는 기법. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴. (= 캐싱, caching)
다이나믹 프로그래밍에 국한된 개념은 아님

• 탑다운/보텀업 방식
  • 다이나믹 프로그래밍의 전형적 형태는 보텀업
  • DP 테이블 : 결과 저장용 리스트

탑다운 (Top-down) 방식

d = [0]*100
def fibo_top(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]

보텀업 (Bottom-up) 방식

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])

→ 메모이제이션 기법을 활용한 계산 과정

• 시간 복잡도가 $O(N)$로 줄어듦.

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

• 부분 문제의 중복에 차이가 있음.
  • 다이나믹 프로그래밍 문제는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
  • 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않음.
    • 분할정복 예시 : 퀵 정렬
      
      한번 Pivot이 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음 → Pivot을 다시 처리하는 부분 문제 X

코딩테스트 대비 방법 ✌

👀 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 중요하다!
그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한 후, 풀이 방법이 떠오르지 않으면 다이나믹 고려하자.

일단 재귀함수로 비효율적인 완전 탐색 프로그램 작성
→ 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있는가?
→ 코드 개선

일반 코테를 대비하기 위해서는 기본 유형만 숙지해도 괜찮다

cf. 최장경로 문제

• 그래프에서 두 정점을 가장 긴 길이로 연결하는 경로 구하기 문제
• A~D의 최장 경로는 [A,C,B,D]인데, A~C의 최장 경로는 [A,C]가 아닌 [A,B,C] 이다.
• 따라서 이러한 문제는 다이나믹 프로그래밍으로 해결하기 어렵다.