그리디
그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다.
하지만 항상 최적의 해를 보장하지 못한다는 단점이 있다.
그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
그리디 알고리즘의 핵심 이론
- 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
- 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
- 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가서 같은 과정을 반복한다.
그리디 알고리즘을 적용하는 문제는 지역적으로 최적이면 전역적으로도 최적인 문제이다.
백준 11047 동전 개수의 최솟값 구하기
https://www.acmicpc.net/problem/11047
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, K;
int cnt;
int price[10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> K;
for (int i = 0; i < N; i++)
{
cin >> price[i];
}
//동전 개수의 최소를 구하려면 가장 큰 값의 동전부터 골라서 목표 값을 채우면 된다.
for (int i = N - 1; i >= 0; i--)
{
while ((K - price[i]) >= 0)
{
K -= price[i];
cnt++;
}
}
cout << cnt;
return 0;
}매번 빼는 방식으로 구현을 했는데, 모듈러 연산을 활용하면 좀 더 효율적일 것이다.
백준 1715 카드 정렬하기
https://www.acmicpc.net/problem/1715
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
priority_queue<int, vector<int>, greater<int>> pq;
int data;
for (int i = 0; i < N; i++)
{
cin >> data;
pq.push(data);
}
int data1 = 0;
int data2 = 0;
int sum = 0;
while (pq.size() != 1)
{
data1 = pq.top();
pq.pop();
data2 = pq.top();
pq.pop();
sum += data1 + data2;
pq.push(data1 + data2);
}
cout << sum;
return 0;
}이 문제는 핵심 아이디어만 뽑아 낸다면 쉽게 구현해서 풀 수 있는 문제다.
카드 더미들 중에서 가장 작은 크기의 더미 두 개를 먼저 더하면 최소 비교 수를 구할 수 있다. 그걸 해내기 위해서는 우선순위 큐를 사용하면 된다.
백준 1744 수 묶기
https://www.acmicpc.net/problem/1744
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
priority_queue<int, vector<int>, greater<int>> minus;
priority_queue<int, vector<int>, less<int>> plus;
int sum = 0;
bool zeroFlag = false;
for (int i = 0; i < N; i++)
{
int data;
cin >> data;
if (data == 0)
zeroFlag = true;
else if (data == 1)
sum += data;
else if (data > 1)
plus.push(data);
else if (data < 0)
minus.push(data);
}
int data1 = 0;
int data2 = 0;
while (plus.size() > 1)
{
data1 = plus.top();
plus.pop();
data2 = plus.top();
plus.pop();
sum += data1 * data2;
}
if (plus.size() == 1)
sum += plus.top();
while (minus.size() > 1)
{
data1 = minus.top();
minus.pop();
data2 = minus.top();
minus.pop();
sum += data1 * data2;
}
if (minus.size() == 1)
{
if(!zeroFlag)
sum += minus.top();
}
cout << sum;
return 0;
}이 문제는 입력 값을 1보다 큰 수/1/0/음수 이 네 종류의 카테고리로 분류해서 처리해야 한다.
1보다 큰 수는 큰 순서대로 2개씩 짝 지어서 수를 묶으면 최대 수가 된다. 홀수개라면 마지막 하나 남는 건 그냥 더하면 된다.
1은 절대 수를 묶으면 안 된다. 최대가 될 수 없기 때문이다. 그냥 1은 바로 더해준다.
0은 그냥 무시할 수 있지만, 0이 적어도 하나가 있는지를 체크해야 한다. 왜냐하면 음수가 홀수개가 들어와서 하나가 남는 경우 그 하나의 음수와 0을 묶어서 음수 덧셈을 막아야 최대값이 나오기 때문이다.
음수는 음수끼리 곱하면 양수이기 때문에 가장 작은 음수 순서대로 2개씩 묶어서 곱해주면 된다. 마지막 남은 음수는 0이 있다면 날리고, 없다면 그냥 더해준다.
백준 1931 회의실 배정
https://www.acmicpc.net/problem/1931
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
//종료 시간을 기준으로 정렬하고, 종료 시간이 같다면 시작 시간 순으로 정렬한다.
vector<pair<int, int>> times;
cin >> N;
for (int i = 0; i < N; i++)
{
int start, end;
cin >> start >> end;
times.push_back({ end, start });
}
sort(times.begin(), times.end());
int count = 0;
int prevEndTime = 0;
for (int i = 0; i < N; i++)
{
if (prevEndTime <= times[i].second)
{
count++;
prevEndTime = times[i].first;
}
}
cout << count;
return 0;
}이 문제는 그리디 알고리즘으로 종료 시간이 가장 빠른 회의들을 우선적으로 배치하면 해결할 수 있는 문제이다.
종료 시간을 기준으로 정렬을 수행하고 만일 종료 시간이 같다면 시작 시간 기준으로 정렬을 수행한다.
이전 회의의 종료 시간을 변수로 따로 저장해서 정렬된 벡터를 순회하면서 가능한 회의들을 카운팅해주면 된다.
백준 1541 잃어버린 괄호
https://www.acmicpc.net/problem/1541
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
vector<string> split(string input, char delimiter);
int mySum(string a);
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int answer = 0;
string example;
cin >> example;
vector<string> str = split(example, '-');
for (int i = 0; i < str.size(); i++)
{
int temp = mySum(str[i]);
if (i == 0)
{
answer = answer + temp;
}
else
{
answer = answer - temp;
}
}
cout << answer << "\n";
return 0;
}
vector<string> split(string input, char delimiter)
{
vector<string> result;
stringstream mystream(input);
string splitdata;
while (getline(mystream, splitdata, delimiter))
{
result.push_back(splitdata);
}
return result;
}
int mySum(string a)
{
int sum = 0;
vector<string> temp = split(a, '+');
for (int i = 0; i < temp.size(); i++)
{
sum += stoi(temp[i]);
}
return sum;
}
문제를 푸는 아이디어는 간단하지만 문자열 처리가 좀 더 귀찮았던 문제이다.
문자열을 split하는 방법을 잘 숙지해두자.
그리디는 생각보다 어려운 알고리즘은 아닌 것 같다.
문제를 딱 봤을 때 그리디로 풀 수 있겠는데? 하는 직관이 잘 와야하는 것 같다.
공부 자료 : Do it! 알고리즘 코딩테스트 C++편 (김종관, 이지스퍼블리싱)
