알고리즘 스터디 첫 주차 주제로 DP가 선정되었다.
악명 높은 DP,, 이번 기회에 부셔버릴테다,, 😠
📌 동적계획법(DP - Dynamic Programming)이란?
전체 문제를 해결하기 위해서 큰 문제를 작은 문제로 쪼개고, 작은 문제들의 답을 가지고 큰 문제를 해결하는 방식이다.
공간 복잡도를 늘리고 시간 복잡도를 줄이는 방법이라고 한다.
=> 시간은 줄이고 메모리 사용은 늘어나는 특징을 가진다.
🤔 왜 DP를 사용할까?
피보나치 수열을 예시로 살펴보자.
피보나치 수열을 구하는 방법은 간단하다.
F(n) = F(n-1) + F(n-2)의 공식대로 계산하면 된다.
이를 재귀방식으로 구현한다면 한다고 해보자.
F(10)을 구하기 위해서는,
1. F(10)을 호출 => 1번
2. F(10)이 F(9), F(8)을 호출 => 2번
3. F(9)가 F(8),F(7)을 호출하고, F(8)이 F(7),F(6)을 호출 => 4번
4. F(8)이 F(7),F(6)을 호출, F(7)이 F(6),F(5)를 호출, F(7)이 F(6),F(5)를 호출, F(6)이 F(5),F(4) 호출 => 8번
...
결국 2^10 = 1024번의 호출이 일어나게 된다.
보면 알 수 있듯이 중복되는 호출이 많이 일어나게 되므로 매우 비효율적이다.
이를 DP로 구현한다면?
결과를 저장해두고 사용하기 때문에 시간 복잡도를 O(n^2) ➡️ O(n)으로 줄일 수 있다.
📌 동적계획법(DP - Dynamic Programming) 적용 조건
DP를 적용하기 위해서는 아래 두가지 조건을 모두 만족해야 한다.
1️⃣ 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제들로 나누어서 해결할 수 있어야 한다.
ex) 피보나치 수열 ➡️ F(n) = F(n-1) + F(n-2)
2️⃣ 중복되는 부분 문제(Overlapping Subproblem)
큰 문제를 쪼갰을 때, 작은 문제가 중복해서 등장해야 한다.
ex) 피보나치 수열 ➡️ 같은 계산을 반복함(위에서는 중복되는 호출을 하는 것)
🤔 큰 문제를 쪼갠다고? 분할정복(divide and conquer)랑 비슷한데?
분할 정복은 문제를 쪼갰을 때, 중복되는 부분이 없을 때도 적용할 수 있지만,
DP는 중복되는 부분이 없다면 적용할 수 없다는 점에서 차이가 존재한다.
📌 동적계획법(DP - Dynamic Programming)의 종류
(Top - '큰 문제', Down - '작은 문제'로 생각하면 조금 편할지도,,)
1️⃣ Top-down(하향식, Memoization)
재귀 호출을 사용해서 문제를 해결한다.
큰 문제를 해결하기 위해서 작은 문제를 호출한다.
작은 문제들을 해결하고 결과를 저장해둔다. ➡️ Memoization(메모지에이션)
결과를 캐싱해두는 것이라고 생각하면 이해하기 쉬울 것 같다.
✅ 장점
필요한 것만 계산한다.
분할정복(Divide and Conquer) 방식과 비슷하다
✅ 단점
재귀가 깊어지면 🚨stack overflow 문제🚨가 발생할 수 있다.
2️⃣ Bottom-up(상향식, Tabulation)
반복문을 사용해서 문제를 해결한다.
작은 문제부터 차례대로 해결하는 방식이다.
작은 문제들을 해결하고 그 결과를 이용해서 더 큰 문제의 결과를 도출한다.
결과를 저장해두고 다음 계산에 이용한다.
✅ 장점
stack overflow 문제가 발생하지 않는다.
✅ 단점
모든 작은 문제들을 계산하기 때문에, 필요하지 않은 것도 계산한다.
📌 동적계획법(DP - Dynamic Programming) 적용하기
해당 문제를 DP로 풀 수 있는지 없는지를 판별하는게 가장 어렵다,,
1. DP를 적용할 수 있는지 따져보기
최적 부분 구조와 중복되는 부분 문제인지를 따져보는 것이다.
2. 점화식 도출하기
F(n)=F(n-1)+F(n-2)와 같은 점화식을 도출해야 한다.
피보나치 수열에서 n=0일때와 n=1일때는 점화식을 적용할 수 없다.
이런 문제는 미리 값을 저장해두는 방법으로 해결이 가능하다.
3. 구현~!
위의 점화식을 기반으로 Top-down이나 Bottom-up 방식으로 구현하면 된다.
📌 관련 백준 문제
첫주는 3문제로 시작했다.
풀다보니 막 그렇게 어려운거 같지는 않은데,,
만약 DP라는 카테고리 없이 문제가 주어졌다면 이 문제를 DP로 풀어야하는지를 알아차리는게 관건인거 같다.
문제를 많이 풀면서 감을 익히는게 중요한 것 같다.
브론즈1
https://www.acmicpc.net/problem/2748
실버3
https://www.acmicpc.net/problem/9095
골드5
https://www.acmicpc.net/problem/2225