[2021 하계 모각코] 1차시

다이나믹 프로그래밍

 

---

한번에 하나의 문제만 풀도록 하는 알고리즘이다.

큰 문제를 작은 문제로 나누어 푸는 문제로서 분할 정복과 비슷하지만 큰문제를 단순히 작은 문제로 나누어 푸는 분할정복과 다르게 다이나믹 프로그래밍은 작은 부분 문제들이 중복으로 일어난다.

​

이런 부분 문제들이 중복으로 일어나는 다이나믹 프로그래밍 방식은 정답을 구한 반복되는 문제들을 어딘가에 메모해놓고 이 메모한 문제를 사용하여 반복되는 문제를 해결한다. 이를 Memoization이라고 한다.

​

대표적인 예로 피보나치 수열이 있다.

피보나치 수열은 재귀적으로 또는 반복문으로 해결할 수 있는데

F[n] = f(n-1) + f(n-2) 의 점화식을 가진다.

구하려는 n번째 수열을 수열의 n-1, n-2값을 사용하여 구하기 때문에 반복적으로 접근하는 문제가 생기고

이때 배열에 해당 문제들을 저장해놓음으로써 해결한다.

​

구현 방식은 Top-down 방식과 Bottom-up 방식으로 나눌 수 있다.

Top-down의 경우 큰문제를 해결할 때 작은 문제가 해결되지 않았다면 그제서야 작은 문제를 해결하여 큰문제를 해결하는 방식이다.

Bottom-up의 경우 작은 문제부터 차례대로 문제를 해결해나가는 방식이다.

​

​

---

백준 문제

https://github.com/miraekwak/BOJ/blob/main/2839.py

GitHub - miraekwak/BOJ