[알고리즘] 5. 동적 계획법

Index

1. 다이나믹 프로그래밍

2. 추천문제

3. 참고자료

---

1.  다이나믹 프로그래밍

Dynamic Programming

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

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음

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

- Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), 

- Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재

- Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용

- 분할 정복은 부분 문제의 중복이 없음

 

(조건)

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

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

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

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

 

(exam)

- 피보나치 수열: (a_n = a_(n-1)+a_(n-2)), a_1 = 1, a_2 = 1

- 시간 복잡도: O(N) 

# 재귀로 구현
def fibo(x):
  if x == 1 or x == 2:
    return 1
  return fibo(x-1) + fibo(x-2)
  
# Top-down 다이나믹 프로그래밍
d = [0] * 100
  
def fibo(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], d[2] = 1, 1
n = 99

for i in range(3,n+1):
  d[i] = d[i-1] + d[i-2]

 

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

- 가장 긴 증가하는 부분 수열을 찾는 문제

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

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

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)

 

 

2.  추천 문제

Dynamic Programming

- N으로 표현(https://school.programmers.co.kr/learn/courses/30/lessons/42895)

- 정수 삼각형(https://school.programmers.co.kr/learn/courses/30/lessons/43105)

- 등굣길(https://school.programmers.co.kr/learn/courses/30/lessons/42898)

- 사칙 연산(https://school.programmers.co.kr/learn/courses/30/lessons/1843)

- 도둑질(https://school.programmers.co.kr/learn/courses/30/lessons/42897)

 

---

참고 자료

[Video: 동빈나의 이코테 2021(다이나믹 프로그래밍)] https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7