그리디(greedy) 알고리즘
그리디 알고리즘은 주어진 순간 순간마다 가장 최선의 선택을 하는 알고리즘 설계 기법이다.
매 순간마다 하는 선택은 최선이지만, 전체로 봤을 때는 최적의 선택이라는 보장을 하지 않는다.
그리디 알고리즘은 100% 최적의 해를 보장하지는 않지만, 계산 속도가 최적의 해를 보장하는 알고리즘에 비해서 빠른 경우가 많다.
그리디 알고리즘은 지금의 선택이 다음 선택에 영향을 미치지 않는 경우에 사용하면 유용하다.
즉, 매 순간마다의 선택이 전체 결과에 서로 독립적인 경우라고 할 수 있다.
요약
•
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법
•
매 순간 좋아 보이는 것만 선택
•
현재의 선택이 나중에 미칠 영향에 대해 고려하지 않는다.
예제 1)
A에서 B를 거쳐서 C로 가는 경로의 최소 거리는?
A에서 B, B에서 C로 가는 경로는 각각 서로 영향을 미치지 않는다. 이런 문제를 해결하는 경우에 그리디 알고리즘은 좋은 선택이 된다.
1) A→B : 최단거리는 (B) 2m
2) B→C : 최단거리는 (2) 2m
결과 : 2 + 2 = 4m
예제 2)
손님에게 거슬러야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원)
→ 가장 큰 화폐 단위부터 돈을 거슬러 줘야 한다.
#include <iostream>
using namespace std;
int n; // 손님에게 받은 돈
int coin[4] = { 500, 100, 50, 10};
int answer; // 거스름돈
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < 4; i++) {
answer += (n / coin[i]);
n %= coin[i];
}
cout << answer;
}
C++
복사
•
시간복잡도 : 동전의 종류만큼 반복을 수행하므로, 동전의 종류가 k라 할 때, O(k)가 된다.
그리디 알고리즘으로 해법을 찾을 때는 그 해법이 정당한지 검토해야 한다.
→ 위의 예시에서 가지고 있는 동전 중, 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전을 종합해 다른 해가 나올 수 없기 때문에 그리디로 해결이 가능함.
예제 3)
다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만들어야 한다.
•
단, 특정 인덱스에 해당하는 수가 연속으로 k번 초과해서 더해질 수 없음
→ 해결 알고리즘 : 제일 큰 수와 k를 초과하지 않을만큼 더하고, 두번째 큰 수를 한번 더하면서 m만큼 더해주면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, k, answer;
int arr[1001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr, arr+n, greater<int>());
int big1 = arr[0];
int big2 = arr[1];
while (1) {
if (m == 0) break;
for (int i = 0; i < k; i++) {
answer += big1;
m--;
if (m == 0) break;
}
answer += big2;
m--;
}
cout << answer;
}
C++
복사
예제 4)
어떠한 수가 1이 될 때까지 2가지 연산이 가능하다. 2가지 연산을 하여 1이 되는 최소의 연산의 수는?
1) N에서 1을 뺀다.
2) N에서 K로 나눈다.
→ 반대로 생각하여 1부터 시작해 1을 더하거나, K를 곱하여 N이 되는 최소의 연산의 수를 구하면 된다.
#include <iostream>
using namespace std;
int main() {
int n, k, answer;
cin >> n >> k;
int num = 1;
while (1) {
if (num == n) break;
if (num * k <= n) {
num *= k;
answer++;
}
else {
num++;
answer++;
}
}
cout << answer;
}
C++
복사