컴공댕이 공부일지
[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이 본문
🔎 그리디 알고리즘(탐욕법)이란?
전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데,
쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다.
단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다.
📖 그리디 알고리즘 문제 출제 경향
단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다.
근사한 해만을 구할 수 있는 경우가 대부분입니다.
그리디 알고리즘은 계산 속도가 빠르기에,
시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다.
그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고,
" 탐욕법을 사용해도 늘 최적해가 구해지는 문제 " 가 출제됩니다.
📚 탐욕법 사용의 정당성 증명
그래서 탐욕법을 사용해도 항상 최적해가 구해지는 문제인지 아닌지, 정당성을 증명해야 하는데
1. 탐욕 선택 속성
: 쪼갠 문제들이 서로 영향을 주지 않고, 전체 정답이 안전하게 보장되는 경우
2. 최적 부분 구조
: 쪼갠 문제의 해답들이 모여, 전체의 정답을 구성하는 경우
위의 두 가지 조건을 만족하면, 그리디 알고리즘을 적용해서 최적해를 구할 수 있습니다.
최적해 계산을 위한 탐욕법 적용의 두 가지 조건을 예시를 들어 좀 더 자세하게 보겠습니다.
1. 탐욕 선택 속성 ( Greedy Choice Property )
: 탐욕법으로 구한 부분 문제의 최적 해가 다음 문제에 영향주지 않고,
안전하게 전체 문제의 최종 최적해를 보장함
탐욕적으로 당장 최적의 값을 선택한다 해도, 안전하게 문제의 최적해가 보장될 때 !
욕심쟁이처럼 좋은 것을 선택해도, 전체 결과에 손해가 없으며, 다음 부분 문제에 영향을 주지 않는 경우 탐욕 선택 속성 조건을 만족하는 것입니다.
2. 최적 부분 구조 ( Optimal Substructure )
: 전체 문제의 해가 부분 문제들의 최적해로 구성됨
탐욕법은 큰 문제를 여러 개로 작게 분할한다고 했었습니다. 이렇게 쪼갠 부분 문제의 최적해가 전체 문제의 최적해로 확장되는 경우를 말합니다.
전체 문제를 작게 쪼개, 각 문제들의 그리디한 최적해를 모아 결합해서 전체 문제의 최적해를 알 수 있다면 이 최적 부분 구조 조건을 만족하는 것입니다.
📝 예시 문제
위에서 본 정당성 증명 과정을 통해,
그리디 알고리즘을 적용해도 최적해가 나오는지를 증명하고 풀어야한다.
백준 11047번 동전 0
https://www.acmicpc.net/problem/11047
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
그리디 알고리즘의 사용 조건 2가지를 만족하는 지 확인해보자.
1. 탐욕 선택 속성 (Greedy Choice Property)
- 부분 문제의 최적해가 다음 문제에 영향을 주지 않고, 안전하게 최적해를 보장한다 !
탐욕적인 방법으로 전체 동전 수를 줄이기 위해, 단순히 가장 큰 값의 동전을 사용한다해도, 다음 단계에 영향을 주지 않는다 !
최종적으로 구해지는 해 (최소 동전 개수) 에도 손해를 끼치지 않는다.
예를 들어, 10원, 50원짜리 동전으로 100원을 표현해야한다.
그렇다면, 50원짜리 2개가 10원짜리 10개보다 적은 수의 동전을 사용한다.
가능한 큰 동전을 써서 최종 동전 사용 개수를 줄이려는 단순하고 탐욕스러운 방식이 손해 없이 최종 정답을 보장한다 !
2. 최적 부분 구조 ( Optimal Substructure )
- 부분 문제의 최적해가 전체 문제의 최적해로 확장된다 !
탐욕적으로 각 단계에서 가능한 제일 큰 값의 동전을 사용하는 것이, 문제가 요구하는 최소 개수의 동전을 사용하는 것이다. 즉, 각 단계마다의 그리디한 최적해가 전체문제의 최적의 해로 확장된다.
예를 들어, 800원을 500원, 100원, 50원짜리 동전으로 나타내려한다.
800 = 100*8 = 500*1 + 100*3
이런 식으로, 100원짜리 8개 대신, 500원 1개 쓰고, 100원을 3개 쓰면 동전 개수가 줄어든다.
즉, 가능한 가장 큰 금액의 동전을 그때그때 쓰는 것이, 최종적으로 동전 개수를 줄이는 문제의 정답으로 확장된다 !
따라서 이 문제에 그리디 알고리즘을 적용해,
매 순간마다 가능한 가장 큰 동전을 사용하며 점차 남은 돈을 줄여나가면,
최소의 동전 개수를 구할 수 있다 :)
(정답 코드)
#include <iostream>
#include <vector>
using namespace std;
// 그리디 알고리즘 활용 : 늘 가능한 가장 큰 동전 사용하기 !
int cntCoins(vector<int>& coins, int k) {
int cnt = 0;
for(int i=coins.size()-1 ; i>=0; i--) { // 오름차순으로 정렬된 동전들. 금액 큰 순서부터 반복문 !
if(coins[i]<=k) { // 현재 남은 금액(k)보다 작은 동전들 중 가장 큰 동전 coins[i]
k-=coins[i]; // 남은 금액에서 현재 사용한 동전만큼 빼기
cnt ++ ; // 사용한 동전 개수 +1
i++; // 현재 동전부터 다음 반복 다시 시작하려고 !
}
}
return cnt;
}
int main()
{
// 속도 향상 코드
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 선언
int n, k, temp;
vector <int> coins; // n개 종류의 동전들 담을 벡터
// 입력
cin >> n >> k;
while(n--) {
cin >> temp;
coins.push_back(temp);
}
// 연산 및 출력
cout << cntCoins(coins, k);
return 0;
}
'CS > 알고리즘' 카테고리의 다른 글
[ 동적계획법 ] top-down, bottom up (상담시간 퇴사 문제) (0) | 2024.04.02 |
---|---|
[ 동적프로그래밍 ] 개념 (피보나치, 외발뛰기) (0) | 2024.04.02 |
[ 비트마스킹 ] 비트마스킹의 정의와 예제 문제 풀이 ( c++ 백준 11723 집합 ) (0) | 2024.03.12 |
[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지 (3) | 2024.03.05 |
[ 정수론 ] 최대공약수 구하기 - 유클리드 호제법 (0) | 2024.03.02 |