1. 동적 계획법(Dynamic Programming, DP)
개념
- 동적 계획법은 작은 부분 문제의 답을 저장하고 재활용하여 전체 문제를 해결하는 기법입니다
- 일반적으로 중복되는 하위 문제(overlapping subproblems)와 최적 부분 구조(optimal substructure)를 가지는 문제에서 사용됩니다.
- 대표적인 예제로는 피보나치 수열, 배낭 문제(Knapsack Problem), 최단 경로 문제 등이 있습니다
동적 계획법을 사용할 수 있는 가정
- 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 마치 피보나치 수열처럼.
- 큰 문제들은 작은 문제들로 이루어진다. 작은 문제들로 분할이 가능.
- 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- 즉, 점화식을 세울 수 있어야 한다.
DP의 두 가지 방식
1. 탑다운 방식 (Top-down, Memoization)
- 재귀를 이용하여 큰 문제를 작은 문제로 나누어 해결하는 방식이다.
- 이미 계산한 값은 저장하여 중복 계산을 피한다.
- 깊은 재귀 호출이 발생할 수 있으므로 스택 오버플로우 방지에 주의해야 한다.
2. 바텀업 방식 (Bottom-up, Tabulation)
- 작은 문제부터 해결하며 점진적으로 큰 문제를 해결하는 방식이다.
- 반복문을 사용하여 결과를 테이블에 저장하고 참조한다.
- 재귀 호출이 없으므로 스택 오버플로우 문제를 방지할 수 있다.
피보나치 수열을 탑다운과 바텀업으로 한번 구현해봤습니다.
피보나치 수열은 대부분이 익숙할 내용이니 그림으로 설명하겠습니다.
딱 보시면 감이 오실 거라 생각합니다. 자신과 자신의 순서 -1 의 수를 더해 자신의 다음 순서에 저장하는 것을 반복합니다.
즉
위와 같은 형태를 띄게 됩니다.
예제 1: 피보나치 수열 (Top-down, Memoization)
#include <iostream>
#include <vector>
using namespace std;
vector<long long> dp(100, -1);
long long fibonacci(int n) {
if (n <= 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
cout << "Fibonacci(" << n << ") = " << fibonacci(n) << "\n";
return 0;
}
예제 2: 피보나치 수열 (Bottom-up, Tabulation)
#include <iostream>
#include <vector>
using namespace std;
long long fibonacci(int n) {
vector<long long> dp(n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
cout << "Fibonacci(" << n << ") = " << fibonacci(n) << "\n";
return 0;
}
0/1 배낭 문제(Knapsack Problem)
문제 설명
- 배낭 문제는 한정된 무게(capacity) 내에서 가장 높은 가치를 얻는 방법을 찾는 문제이다.
n개의 아이템이 주어지며, 각 아이템은무게(weight)와가치(value)를 가진다.- 아이템을 한 번만 선택할 수 있으며(0/1 선택), 무게 한도를 초과할 수 없다.
해결 방법
dp[i][w]는i번째 아이템까지 고려했을 때, 무게w이하에서의 최대 가치를 저장하는 2차원 배열이다.- 점화식:
- 만약 현재 아이템의 무게가
w보다 작다면, 해당 아이템을 선택할 수 있음. dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])- 그렇지 않다면, 해당 아이템을 선택하지 않음.
dp[i][w] = dp[i-1][w]
- 만약 현재 아이템의 무게가
코드 구현 (Bottom-up Approach)
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (weights[i - 1] <= w)
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}이제 백준 문제를 통해 배낭 문제를 알아보고자 합니다. (https://www.acmicpc.net/problem/12865)
(https://sectumsempra.tistory.com/103) 를 참고해 작성된 예시입니다.
설명을 너무 잘 해주셔서 가져왔습니다.
해당 문제를 요약하자면
짐 4개가 다음과 같이 있을 때, 7kg까지 넣을 수 있는 가방에 넣을 수 있는 짐의 가치의 최대합은 얼마인가?
| 무게 | 가치 |
|---|---|
| 6 | 13 |
| 4 | 8 |
| 3 | 6 |
| 5 | 12 |
해결 방법 (아이디어)
- [짐의 수+1][무게+1] 크기의 배열을 생성합니다. 위 문제의 경우 짐이 4개이고 가방에 7kg까지 담을 수 있으니 아래와 같이 표를 생성합니다.
- 칸을 채워나간다. 우선 첫 번째 행의 경우는 가방에 무게6, 가치 13의 짐을 넣으려 하는 경우인데, 1~5kg까지 담을 수 있다고 가정하면 이 짐은 넣을 수 없고, 6,7kg까지 담을 수 있다고 하는 경우에만 짐을 넣을 수 있습니다.
즉 담을 수 없는 경우엔 0 이라는 값을 넣어줍니다.
최대 7kg까지 담을 수 있다고 했기 때문에 두 번째 짐도 넣어보면
여기서 주목할 점은 배열[2][6] , 배열[2][7]입니다. 가치 8짜리 짐을 넣는 것 보다 13짜리 짐을 넣는 것이 이득이기 때문에 바로 윗칸의 값, 즉 배열[1][6], 배열 [1][7]부분을 각각 가져오고 있습니다.
이제 3,6짜리 짐을 넣는다고 하면 여기서는 배열[3][7]부분에 주목해야 합니다. 단순히 윗칸의 값을 가져오는 것보다 가치 8짜리 짐(2번 짐)과 가치 6인 짐(3번짐)을 넣는 것이 이득이기 때문에 값 14가 들어갑니다.
이를 알고리즘의 점화식으로 표현한다면!
현재 짐을 넣을 수 있다.
짐을 넣는다.
-> 배열[i-1][W-현재 짐의 무게] + 현재 짐의 가치 값을 넣는다.
짐을 넣지 않는다.
-> 윗 칸의 값을 가져온다.
현재 짐을 넣을 수 없다.
짐을 넣지 않는다.
-> 윗 칸의 값을 가져온다.이런 식으로 정리할 수 있겠죠 ?
짐을 넣는 경우는 바로 위의 경우를 보면 됩니당. 3번째 짐을 넣을지 말지 검토할 때 무게 7까지 넣을 수 있다면, 2번 짐(무게 4, 가치 8)의 짐을 넣고 3번 짐을 넣습니다. 즉 배열[3][7]에 배열[2][7-3번짐의 무게(3)]+3번 짐의 가치(6) 값을 넣습니다.
우리는 7kg까지 담을 수 있을 때의 최대 가치를 알고싶으니 배열[4][7]이 답이다. 즉 14가 답이 된다.
이를 C++ 코드로 작성하면! (블로그내 c++ 코드입니당)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define P pair<int,int>
using namespace std;
//[물품 수][무게]
int arr[101][100001];
int allweight[101];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, w, v;
cin >> n >> k;
//(무게,가치)의 쌍을 담는 벡터 vv
vector<P> vv;
for (int i = 0; i < n; i++) {
cin >> w >> v;
vv.push_back(P(w, v));
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
int curweight = vv[i-1].first;
int curval = vv[i-1].second;
//현재 검토중인 짐을 담을 수 있는 경우(두 경우 중 최적의 경우 선정->max함수 사용)
//1. 현재 짐을 넣지 않는다(바로 윗 칸의 값을 가져온다.) arr[i-1][j]
//2. 현재 짐을 넣는다.arr[i-1][j-curweight]+curval
if (curweight <= j) {
arr[i][j] = max(arr[i - 1][j - curweight] + curval, arr[i - 1][j]);
}
//현재 검토중인 짐을 담을 수 없는 경우
//바로 윗 칸의 값을 가져온다. arr[i-1][j]
else {
arr[i][j] = arr[i - 1][j];
}
}
}
cout << arr[n][k];
}2. 그리디 알고리즘(Greedy Algorithm)
개념
- 그리디 알고리즘은 매 순간 최적이라고 생각되는 선택을 하면서 전체 해를 구하는 방법이다.
- 항상 최적해를 보장하지는 않지만, 특정 조건에서 최적해를 보장하는 문제들이 존재한다.
- 대표적인 예제로는 거스름돈 문제, 활동 선택 문제(Activity Selection), 크루스칼 알고리즘 등이 있다.
그리디 알고리즘 단계
💡 그리디 알고리즘의 단계는 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미합니다.
💡 그리디 알고리즘의 단계
문제의 최적해 구조를 결정합니다.
문제의 구조에 맞게 선택 절차를 정의합니다 : 선택 절차(Selection Procedure)
- 이 단계에서는 ‘현재 상태’에서 ‘최적인 선택’을 합니다. 이 선택은 이후에는 바뀌지 않습니다.
선택 절차에 따라 선택을 수행합니다.
선택된 해가 문제의 조건을 만족하는지 검사합니다 : 적절성 검사(Feasibility Check)
- 이 단계에서는 선택한 항목이 ‘문제의 조건’을 만족시키는지 확인합니다. 조건을 만족시키지 않으면 해당 항목은 제외됩니다.
조건을 만족하지 않으면 해당 해를 제외합니다.
모든 선택이 완료되면 해답을 검사합니다 : 해답 검사(Solution Check)
- 이 단계에서는 모든 선택이 완료되면, ‘최종 선택’이 ‘문제의 조건을 만족’시키는지 확인합니다. 조건을 만족시키면 해답으로 인정됩니다.
- 조건을 만족하지 않으면 해답으로 인정되지 않습니다.
예제 1: 거스름돈 문제
문제 설명
- 거스름돈 문제는 가장 적은 수의 동전으로 특정 금액을 거슬러 주는 문제이다.
- 다양한 동전 단위가 주어질 때, 최소 개수의 동전을 사용하여 거스름돈을 만드는 방법을 찾는다.
- 탐욕적 기법을 사용할 수 있는 경우는 큰 단위의 동전이 작은 단위의 동전의 배수인 경우이다. 그렇지 않은 경우 최적해를 보장하지 못할 수도 있다.
해결 방법
- 가장 큰 단위의 동전부터 최대한 사용하면서 남은 금액을 처리한다.
- 해당 단위를 사용한 후, 남은 금액을 더 작은 단위의 동전으로 반복하여 처리한다.
#include <iostream>
#include <vector>
using namespace std;
int minCoins(int amount, vector<int>& coins) {
int count = 0;
for (int coin : coins) {
count += amount / coin;
amount %= coin;
}
return count;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int amount;
cin >> amount;
vector<int> coins = {500, 100, 50, 10};
cout << "Minimum coins needed: " << minCoins(amount, coins) << "\n";
return 0;
}
예제 2: 회의실 배정 문제(Activity Selection)
문제 설명
- 활동 선택 문제는 한 사람이 여러 개의 활동 중에서 최대한 많은 활동을 선택할 수 있도록 하는 문제이다.
- 각 활동은 시작 시간과 종료 시간이 있으며, 겹치지 않도록 선택해야 한다.
- 탐욕적 기법을 사용할 수 있는 경우는 빨리 끝나는 활동을 먼저 선택하는 방식을 따를 때이다.
해결 방법
- 종료 시간이 가장 빠른 활동을 먼저 선택한다.
- 그 이후 선택한 활동과 겹치지 않는 활동 중에서 다시 종료 시간이 가장 빠른 것을 선택하는 방식으로 진행한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Meeting {
int start, end;
};
bool compare(Meeting a, Meeting b) {
return a.end < b.end;
}
int maxMeetings(vector<Meeting>& meetings) {
sort(meetings.begin(), meetings.end(), compare);
int count = 0, lastEnd = 0;
for (auto& meeting : meetings) {
if (meeting.start >= lastEnd) {
count++;
lastEnd = meeting.end;
}
}
return count;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
vector<Meeting> meetings(n);
for (int i = 0; i < n; i++) {
cin >> meetings[i].start >> meetings[i].end;
}
cout << "Maximum number of meetings: " << maxMeetings(meetings) << "\n";
return 0;
}
3) 그리디 알고리즘과 DP
💡 비슷한 방법으로 해결이 되는 동적 계획법과 비교를 해봅니다.
| 분류 | 그리디 알고리즘(Greedy Algorithm) | 동적 계획법(DP: Dynamic Programming) |
|---|---|---|
| 설명 | 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 | 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 |
| 성립 조건 | 1. 탐욕 선택 속성(Greedy Choice Property)2. 최적 부분 구조(Optimal Substructure) | 1. 중복 부분 문제 (Overlapping Subproblems)2. 최적 부분 구조 (Optimal Substructure) |
| 중복 부분 문제 | 중복 부분 문제를 해결하지 않습니다. | 중복 부분 문제를 해결할 수 있습니다. |
| 상황 | - 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다.- 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다. | - 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다- 모든 상황을 계산하기에 시간이 오래 걸립니다. |
DP는 큰 문제를 작은 문제로 나누어 해결, 그리디는 각 단계에서 최적 선택을 한다는 차이가 있습니다. 상황에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.
