DP : 넷플릭스 DP만큼 다이나믹한(?) 프로그래밍 룰루..ㅎ
📖 동적 계획법이란?
✅ 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제들의 정답을 결합하여 알고리즘을 푸는 과정
✅ 복잡한 문제의 규칙을 찾아 간단한 여러 개의 문제로 나누어 푸는 방법
✅ 특히 하위 문제의 수가 기하급수적으로 증가할 때, 계산 횟수를 줄여 적은 시간 내에 문제를 품
✅ 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용
ㄴ 큰 문제를 잘게 쪼개어 풀기
1. 동적 계획법 vs 그리디 알고리즘
예시 상황)
오늘은 월요일, 플레이데이터 수업을 듣기 위해 등원해야한다.
그런데 지금은 벌써 9:30..?!?!? 지각이다.
최단 경로, 출근 시간의 차량 정체, 신호, ... 고려해야할 사항이 너무 많다.
A: 최단 경로, 최단 시간을 철저히 계산한 뒤 그 경로로 출발할까?
B: 일단 한 시라도 일찍 출발해서 그 때 그 때 가장 짧아보이는 길을 선택할까?
위 상황에서 A 방식이 동적 계획법, B 방식이 그리디 알고리즘에 해당한다.
동적 계획법은 큰 문제를 잘게 쪼개어 푼다.
최단 시간으로 등원하기 위한 경로 탐색 이라는 크고 복잡한 문제를
최단 경로 탐색, 해당 시간 교통 상황 확인, 최적 교통 수단 탐색 등 작은 문제로 쪼개어 모든 경우를 확인한다.
이후, 최적의 경로를 찾아낸다.
이 방법의 경우, 문제를 풀어내는 시간 자체에 시간이 걸리겠지만 현 상황에서 최단 시간에 등원할 수 있는 답을 찾는다.
그리디 알고리즘은 멀리 보지 않고, 눈 앞의 갈림길만 고려한다.
그리디 알고리즘을 사용한다면, 일단 앞뒤 재지않고 당장 출발해야한다.
당장 나가서 갈림길을 마주하면, 이 갈림길만 두고 봤을 때 보다 학원에 가까운 길을 선택한다.
운이 좋아 전체적으로 보았을 때도(global) 최적의 경로를 찾는다면, 빠르게 문제를 해결할 수 있다.
하지만, 그리디 알고리즘은 늘 최적의 답을 보장하지 않는다.
갈림길만 놓고 보았을 때(local) 분명 학원 쪽에 더 가까운 길을 선택했음에도 그 길을 따라가다보니 막다른 길일수도 있고, 돌아가는 길일수도 있다.
2. 동적 계획법 구현 방식
1) Bottom up
- 작은 문제에서 큰 문제로 아래에서부터 풀어가는 방식
반복문으로 구현피보나치 수열 연산 시,
fibo(1) = 1
fibo(2) = 1
fibo(3) = fibo(1) + fibo(2) = 1 + 1 = 2
fibo(4) = fibo(2) + fibo(3) = 1 + 2 = 3
...
fibo(n) = fibo(n-2) + fibo(n-1)
위 방법처럼 아래에서부터 반복적으로 큰 문제로 나아가는 방식이 bottom up이다.
2) Top down
- 큰 문제에서 작은 문제로 위에서부터 풀어가는 방식
재귀로 구현팩토리얼 연산 시,
factorial(n) = n factorial(n-1)
= n (n-1) factorial(n-2)
= n (n-1) (n-2) factorial(n-3)
...
= n (n-1) (n-2) ... 3 2 1
위 방법처럼 위에서부터 재귀적으로 작은 문제로 나아가는 방식이 top dowm이다.
3. 메모이제이션(Memoization)
✔ 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써
✔ 동일한 계산의 반복 수행을 제거, 프로그램 실행 속도를 빠르게 하는 기술
- 위 피보나치 수열 연산에서는 fibo(n)을 연산할 때, 이전 연산인
fino(n-2),fino(n-1)을 미리 연산하여 어딘가에 저장해두고 이를 불러와 다음 연산을 진행, 중복 연산을 방지한다. - 위 팩토리얼 연산에서는 factorial(n)을 연산할 때, 이전 연산인
n * (n-1) * (n-2) ...을 미리 연산하여 어딘가에 저장해두고 이를 불러와 다음 연산을 진행, 중복 연산을 방지한다.
