다이나믹 프로그래밍
🎯 Keyword : DP, Memoization
1. 다이나믹 프로그래밍이란
1-1. 개론
DP(Dynamic Programming)는 문제를 여러 작은 부분문제로 쪼개고 부분문제의 답을 재사용함으로써 속도를 빠르게 하는 기법이다.
동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. - 위키피디아
1-2. Memoization
DP를 적용할 때 가장 중요한 문제의 성질은 중복되는 부분문제이다. 예를 들어 피보나치 수열을 구하는 알고리즘의 흐름을 살펴보자.
이 그림에서 f(2)는 3번, f(3)은 2번 호출되고 있다. 그렇다면 이들을 한 번 계산해둔 뒤에 다시 사용할 수 없을까? 예를 들어 f(2)를 계산해서 저장한 뒤에 필요할 때마다 불러와 사용한다면 f(2)를 1번만 호출해도 될 것이다. 바로 이것이 Memoization의 기본 아이디어다.
1-3. Top-Down
DP를 적용하는 방법으로는 Top-Down과 Bottom-Up이 있다. Top-Down은 큰 문제를 점차 작은 문제들로 쪼개어나가는 방법이다. Bottom-Up 방식에 비해 직관적이라는 장점이 있다.
1-4. Bottom-Up
Bottom-Up은 큰 문제를 해결할 때 필요할 것으로 예상되는 작은 문제들을 미리 해결한 뒤, 그를 조합해 큰 문제를 해결하는 방법이다.
2. 문제
3-1. 피보나치 함수 - 백준
👀 살펴보기
문제 : DP를 이용해 피보나치 수열을 효율적으로 구하는 문제
🎨 지도 및 설명
✅ 정답 소스코드
3-2. 이항 계수 2 - 백준
👀 살펴보기
문제 : DP를 이용해 이항계수를 효율적으로 계산하는 문제
🎨 지도 및 설명
✅ 정답 소스코드
3-3. 1, 2, 3 더하기 - 백준
👀 살펴보기
문제 : 주어진 수를 1,2,3의 합으로 나타내는 방법의 가짓수를 구하는 문제
🎨 지도 및 설명
✅ 정답 소스코드
3-4. SCV 자원채취 - 더블릿
👀 살펴보기
문제 : 2차원 DP
🎨 지도 및 설명
- 각 지점에서 가질 수 있는 최대 미네랄 양을 저장하는 방식으로 DP를 적용할 수 있음.
✅ 정답 소스코드
3-5. 긋기 게임 - 더블릿
👀 살펴보기
문제 :
🎨 지도 및 설명
✅ 정답 소스코드
3-6. LIS - 백준
👀 살펴보기
문제 : LIS
