코딩테스트에서 많이 사용되는 dynamic programming(다이나믹 프로그래밍, 동적 계획법)의 개념과 언제 어떻게 사용할 수 있는지 두 가지 예제를 통해 살펴봅니다~

https://youtu.be/GtqHli8HIqk

Optimization problem

- 문제를 해결하는 최적의 답을 찾아야 하는 문제

- optimal solution은 하나 이상일 수 있다.

- maximum 혹은 minimum value를 가지는 솔루션을 찾는 문제들이 주를 이룬다.

- ex) 가장 빨리 도착하는 경로의 소요 시간은? 언제 주식을 사고 팔 때 가장 수익이 높은지?

 

다이나믹 프로그래밍(DP, Dynamic programming)

- optimization problem을 해결하는 전략 중 하나

- subproblem(s)의 optimal solution(s)을 활용해서 문제의 optimal solution을 찾는 방식

- 겹치는(overlapping) subproblems은 한 번만 계산하고 그 결과를 저장한 뒤 재사용한다.

 

DP의 두 가지 접근 방식

	Top-Down approach	Bottom-Up approach (주로 사용)
구조	recursive	iterative
subproblem 결과 저장	memoization	tabulation
언제 선호되는지?	subproblems의 일부만 계산해도 최종 optimal solution을 구할 수 있을 때	모든 subproblems를 계산해야 최종 optimal solution을 구할 수 있을 때

 

알고리즘 설계 순서

1. 주어진 문제의 optimal solution이 구조적으로 어떤 특징을 가지는지 분석

2. 재귀적인 형태로 optimal solution의 value를 정의

3. (주로) Bottom-Up 방식으로 optimal solution의 value를 구한다.

(4. 지금까지 계산된 정보를 바탕으로 optimal solution을 구한다.)

 

DP를 사용하기 위해 확인해야 할 두 가지 조건

1. optimization problem이 optimal substructure여야 한다.

- optimization problem의 optimal solution이 subproblem(s)의 optimal solution(s)을 포함하는 구조

- subproblems는 독립적이어야 한다. => subproblem의 solution은 다른 subproblem solution에 영향을 줘선 안 된다.

2. optimization problem이 overlapping subproblems을 가져야 한다.

- 재귀적 형태의 알고리즘이 동작할 때 동일한 subproblems을 여러 번 해결해야 한다면 이 optimization problem은 overlapping subproblems을 가진다고 표현한다.