알고리즘 설명
Greedy Strategy : 지금 당장 좋아보이는 것을 선택하는 전략
- 미래의 상황은 고려하지 않음
- Greedy Strategy를 사용하는 알고리즘을 Greedy Algorithm이라 한다.
항상 최적해를 보장하지는 않음
Local optimum != Global optimum
왜?
현재의 선택이 미래에 미칠 영향을 고려하지 않았기 때문에
그러나, 그리디 알고리즘으로 최적해를 찾을 수 있는 문제도 존재한다.
그리디로 최적해를 찾기 위한 두 가지 조건
- Greedy choice property: 현재의 선택이 최적해에 기여함
- Optimul substructure property: 작은 문제의 정답이 큰 문제의 정답에 포함됨
이 둘을 만족한다면 그리디로 풀 수 있다.
교환증명
첫 번째 조건을 증명하기 위한 방법 중 하나.
- 문제를 푸는 두 가지 방법을 가정
- G: 그리디 알고리즘이 만든 최적해
- O: 임의의 최적해
- 그리디가 첫 단계에서 고른 선택을 g라 하고, O에 g가 포함되어 있지 않다면 O에서 일부 요소를 골라 g와 교환하여 여전히 가능한 해이고 해의 품질이 그대로 유지되는 새로운 해 O'를 만든다.
- 이렇게 하면 O'는 g를 포함하면서도 최적해의 특성을 잃지 않는다.
- 결국 g는 어떤 최적해에도 포함될 수 있는 안전한 선택임이 증명된다.
연습문제
BOJ_11047번: 동전 0
문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
예제 출력 1
6
풀이
#include <bits/stdc++.h>
using namespace std;
array<int, 12> arr;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N, K;
cin >> N >> K;
for(int i = 0; i < N; i++) cin >> arr[i];
int cnt = 0;
for(int i = N-1; i >= 0; i--){
int tmp = K / arr[i];
K = K % arr[i];
cnt += tmp;
}
cout << cnt;
return 0;
}팁
동전 종류가 최대 10개이다.
완전탐색은 가능한 모든 동전 조합을 시도해서 합이 K가 되는 경우를 찾고, 그 중에서 동전 개수가 가장 적은 경우를 선택하는 방식이다.
개수가 동적으로 결정되므로 정확한 시간복잡도를 산정하는 것 조차 어렵다.
완탐 실패 => DP하기엔 K가 너무 큼 => 그리디?
제일 큰 동전을 먼저 다 쓰고, 그다음 크기의 동전을 쓰고...이 순서
그렇다면 그리디의 성립 두 가지 조건을 알아보자.
- Greedy choice property:
제일 큰 수를 A라 하고 그 다음 큰 수를 B라고 하자.
A가 아닌 B를 선택하여 가상의 최적해 O'가 있다고 가정해보자.
A는 B의 배수이므로, B를 제거하고 A를 넣으면 동전 수가 줄어드므로 더 좋은 최적해가 나온다.
- Optimul substructure property
현재 제일 큰 동전을 고르는게 (local optimum)
BOJ_1931번: 회의실 배정
회의실 배정 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 263321 90142 61998 31.765%
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
예제 입력 1
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력 1
4
풀이
#include <bits/stdc++.h>
using namespace std;
array<pair<int,int>, 100004> myTime;
struct myCompare{
bool operator()(const pair<int,int> a, const pair<int,int> b){
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
for(int i = 1; i <= N; i++){
int start;
int end;
cin >> start >> end;
myTime[i] = make_pair(start, end);
}
sort(myTime.begin()+1, myTime.begin() + N + 1, myCompare());
int cnt = 1;
int curStart = myTime[1].first;
int curEnd = myTime[1].second;
for(int i = 2; i <= N; i++){
if(myTime[i].first < curEnd) continue;
curStart = myTime[i].first;
curEnd = myTime[i].second;
cnt++;
}
cout << cnt;
return 0;
}팁
정렬을 한다면 기준이 되는 항목을 제외하고는 오름차순으로 정렬하자.
그래야 실수를 방지한다.
예를들어
(시작시간, 종료시간) 쌍이 다음과 같을 때
(1, 2)
(2, 2)
(2, 3)
선택되는 것은 (1, 3), (2, 2), (2, 3) 이 된다.
하지만
(2, 2)
(1, 2)
(2, 3)
순서로 돈다면 (2, 2), (2, 3) 이 선택되므로 결과가 달라진다.
이 문제는 완전탐색일 경우 O(2^N), DP일 경우 O(N^2)이다.
따라서 그리디를 의심해봐야 한다.
그리디 조건 1 - greedy choice property
A, B, C 순서로 회의가 끝난다고 가정하자.
A를 선택하는 것이 최적해인게 맞는지 증명하자.
A가 아닌 B를 선택했을 때 나오는 최적해가 O'이다.
B는 A보다 늦게 끝난다.
B대신 A를 넣어도 최적해 O'와 동일한 퀄리티의 최적해가 나온다.
따라서 A를 선택하는 것은 최적해에 기여한다.
그리디 조건 2 - optimul substructure property
전체 회의 중에 제일 빨리 끝나는 A 선택
A를 제외한 전체 회의 중에 제일 빨리 끝나는 B선택
이렇게 작은 문제의 정답이 전체 문제의 정답에 포함된다.
BOJ_2217번: 로프
문제
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1
2
10
15
예제 출력 1
20
풀이
#include <bits/stdc++.h>
using namespace std;
array<int, 100004> arr;
struct myCompare{
bool operator()(const int a, const int b){
return a > b;
}
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> arr[i];
sort(arr.begin() + 1, arr.begin()+N + 1, myCompare());
int mx = 0;
for(int i = 1; i <= N; i++){
mx = max(mx, arr[i] * i);
}
cout << mx;
return 0;
}팁
"미래의 선택을 생각하지 않고 현재의 선택에 최선의 것을 고른다"라는 말에 매몰되면 입력배열값 전체를 한 묶음으로 볼 수 없게 된다.
전체 배열을 대상으로 생각해보자.
입력배열을 전체 정렬해서 튼튼한 로프부터 줄세워보자.
상식적으로 약한 로프에 손이 가겠나? 튼튼한 로프부터 손이 가겠나?
튼튼한쪽을 고를 것이다.
제일 튼튼한 로프 x 1 , 두 번째로 튼튼한 로프 x 2, 세 번째로 튼튼한로프 x 3 ...
제일 약한 로프 x n 중에 값이 제일 큰거를 고르면 된다.
그리디 증명 : 교환(교체) 증명 스케치
어떤 최적해가 있다고 가정하고 그 최적해에서 사용된 k개의 로프 중에 상위 k개의 집합에 포함되지 않은 로프 x가 있다고 하자.
상위 k집합에는 x보다 강한 로프 y가 있다(정렬 기준상).
x를 y로 교체하면 k번째(최소) 내구도는 감소하지 않는다. 따라서 arr[k]×k 값은 줄어들지 않거나 증가한다.
이 과정을 반복하면 어떤 최적해도 항상 “상위 k개” 형태로 바꿀 수 있다.
BOJ_2457번: 공주님의 정원
문제
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.
총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)
이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.
공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.
출력
첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.
예제 입력 1
4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10
예제 출력 1
2
풀이
#include <bits/stdc++.h>
using namespace std;
int toDay(int m, int d){
static int mdays[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int day = 0;
for(int i=1;i<m;i++) day += mdays[i];
day += d;
return day;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if(!(cin >> N)) return 0;
vector<pair<int,int>> v;
for(int i=0;i<N;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
int s = toDay(a,b);
int e = toDay(c,d);
// 유효한 꽃만 저장: 종료일 > 시작일(자기날 포함 규칙에 따라)
if(e <= toDay(3,1)) continue; // 3/1 이전에 다 지는 꽃은 무의미
if(s > toDay(11,30)) continue; // 11/30 이후에 피는 꽃도 무의미
v.push_back({s,e});
}
sort(v.begin(), v.end()); // 시작일 오름차순, 같은 시작이면 end 오름차순
int targetStart = toDay(3,1);
int targetEnd = toDay(11,30);
int idx = 0;
int cnt = 0;
int cur = targetStart;
while(cur <= targetEnd){
int bestEnd = cur;
while(idx < (int)v.size() && v[idx].first <= cur){
bestEnd = max(bestEnd, v[idx].second);
idx++;
}
if(bestEnd == cur){
cout << 0 << '\n';
return 0;
}
cur = bestEnd;
cnt++;
}
cout << cnt << '\n';
return 0;
}팁
특정 날짜를 1월 1일기준으로부터 "지난 날"로 정의했다.
이는 1월 1일로부터의 "거리"로 볼 수 있다.
날짜를 "거리"로 변환하는 아이디어를 기억하자.
"그리디 + 거리" 마치 그래프와 같다.
메인 코드의 설명은 다음과 같다.
int idx = 0; // 정렬된 꽃 벡터 v를 순회할 인덱스; 한 번 증가하면 다시 뒤로 돌아가지 않음
int cnt = 0; // 현재까지 선택한 꽃의 개수
int cur = targetStart; // 아직 덮어야 할 구간의 시작점(초기에는 3/1의 day 값)
while (cur <= targetEnd) { // 목표 끝(11/30)까지 덮을 때까지 반복
int bestEnd = cur; // 이 단계에서 cur 이하로 시작하는 꽃들 중 찾은 최대 연장 끝값(초기값은 연장 불가 상태)
// cur 시점에 이미 피어있는(시작일 <= cur) 모든 꽃을 고려하여 그 끝 중 최대를 찾는다
while (idx < (int)v.size() && v[idx].first <= cur) {
bestEnd = max(bestEnd, v[idx].second); // 이 꽃을 사용하면 cur를 어디까지 연장할 수 있는지 갱신
idx++; // 이 꽃은 한 번 검사했으니 다음 꽃으로 넘어감 (다음 반복에서 다시 보지 않음)
}
if (bestEnd == cur) { // 검사한 꽃들로도 cur를 단 한 칸도 연장하지 못했다면
cout << 0 << '\n'; // 목표 구간을 완전하게 덮을 수 없으므로 불가능을 의미하는 0 출력
return 0; // 프로그램 종료
}
cur = bestEnd; // 가장 멀리 연장할 수 있는 끝으로 cur를 갱신(선택한 꽃 한 개로 구간을 연장한 결과)
cnt++; // 위에서 한 번 꽃을 선택했으므로 선택 횟수 증가
}이 문제는 DP로도 풀 수 있다.
조금 복잡하긴 하지만, DP를 공부하는 입장에서는 도움이 된다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int START, TARGET;
vector<pair<int,int>> intervals;
int memo[400]; // 365일인데 넉넉하게 400
int toDay(int m, int d){
static int mdays[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int day = 0;
for(int i = 1; i < m; ++i) day += mdays[i];
day += d;
return day;
}
int solve(int day){
if(day >= TARGET) return 0;
if(memo[day] != -1) return memo[day];
int best = INF;
// 모든 꽃 중에서 시작 <= day 이고 끝 > day 인 것들을 시도
for(const auto &it : intervals){
int l = it.first;
int r = it.second;
if(l <= day && r > day){
int cand = solve(r);
if(cand < INF) best = min(best, 1 + cand);
}
}
memo[day] = best;
return best;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
START = toDay(3,1);
TARGET = toDay(12,1); // exclusive (12/1)
for(int i = 0; i < N; ++i){
int a,b,c,d;
cin >> a >> b >> c >> d;
int l = toDay(a,b);
int r = toDay(c,d); // flower covers [l, r)
// 유효한 꽃만 남김: r > START && l < TARGET
if(r <= START) continue;
if(l >= TARGET) continue;
intervals.push_back({l, r});
}
fill(memo, memo+400, -1);
int ans = solve(START);
if(ans >= INF) cout << 0 << '\n';
else cout << ans << '\n';
return 0;
}중간에 상태 전이가 되지 않을 때, 즉 길이 끊겼을 때는 기저조건에 도달하지 않는다.
백트래킹에서는 기저조건에 도달하지 않더라도 리턴을 해버리면 되지만, 여기서는 기저조건에 도달할 때와 중간에 끊겼을 때를 분리해야 한다.
기저조건에 도달하면 0을 반환하기때문에 도달하지 않은 상태는 "무한"을 반환한다.
