-
그리디 알고리즘 (Greedy Algorithm)코딩 테스트/코딩 테스트 알고리즘 2022. 10. 26. 12:03
01. 그리디 알고리즘이란?
- 현재 상황에서 가장 좋은 것만 고르는 방식이다.
- 탐욕법이라고도 한다.
- 사전에 특정 알고리즘을 공부하지 않아도 풀이를 떠올릴 수 있는 경우가 많다.
02. 그리디 알고리즘의 예시 : 거스름돈 문제
내가 가게의 계산 직원이라고 생각했을 때, 거스름돈이 500원, 100원, 50원, 10원 단위로 있다고 생각하자.
손님에게 거슬러 줘야 할 돈이 N원일 때, 가장 적은 동전을 써서 거슬러줄 수 있는 경우는?- 전형적인 그리디 알고리즘의 예시
- "가장 큰 화폐 단위부터" 돈을 거슬러 주면 됨
- 1370원을 거슬러 줘야 한다고 가정할 때
- 가장 큰 단위인 500원을 2번 거슬러 준다. (남은 돈 370원)
- 두 번째 큰 단위인 100원을 3번 거슬러 준다 (남은 돈 70원)
- 세 번째 큰 단위인 50원을 2번 거슬러 준다. (남은 돈 20원)
- 가장 작은 단위인 10원을 2번 거슬러 준다. (남은 돈 0원)
- 결과적으로 2 + 3 + 2 + 2 = 11개가 가장 적게 쓸 수 있는 동전 개수
- 다음 수행에 상관없이 일단 가장 많이 거스름돈을 깎을 수 있는 단위를 사용한다는 것이 중요
03. 그리디 알고리즘의 정당성 판별
- 중요한 것은, 지금 상황에서 가장 좋은 것만을 골라도 문제를 풀 수 있는지를 파악하는 것이 중요
- 기준에 따라 좋은 것을 선택하는 알고리즘이므로, "특정 기준"을 제시해주는 경우가 많다.
- "가장 작은 순서대로", "가장 큰 순서대로"
- 거스름돈 문제에 그리디 알고리즘을 적용할 수 있었던 이유는?
- 가지고 있는 동전 개수가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문
- 예를 들어, 500원, 400원, 100원인 경우 800원을 거슬러 줘야 한다고 했을 때
- 그리디 알고리즘을 적용하면 500 + 100 + 100 + 100 => 4번이지만
- 400 + 400으로 다른 최적해가 존재한다.
- 정당성을 검토해보고, 그렇지 못하다면 동적 프로그래밍이나 그래프 알고리즘을 고민해보자.
04. 실전 문제 풀이
1. 큰 수의 법칙
더보기// 그리디 알고리즘 >> p.92 큰 수의 법칙 #include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { int n, m, k; cin >> n >> m >> k; vector<int> nums(n); for (int i = 0; i < n; ++i) { cin >> nums[i]; } // 첫 작성 답안 // { // int answer = 0; // int max = -1, max2 = -1; // // for (int i = 0; i < n; ++i) // { // if (max <= nums[i]) // { // max2 = max; // max = nums[i]; // } // } // // int cnt = 0; // while (m > 0) // { // if (cnt == 3) // { // answer += max2; // cnt = 0; // } // else // { // answer += max; // ++cnt; // } // --m; // } // // cout << answer; // } // // 개선된 버전 { int answer = 0; int max = -1, max2 = -1; sort(nums.begin(), nums.end(), greater<int>()); // 가장 큰 수와 두번째로 큰 수 max = nums[0]; max2 = nums[1]; // 가장 큰 수 등장 횟수 int maxCount = (m / (k + 1)) * k + (m % (k + 1)); answer += maxCount * max; answer += (m - maxCount) * max2; cout << answer; } return 0; }- "가장 큰 수"를 무조건 많이 더해야 하므로, 그리디 알고리즘이라고 할 수 있음
- k번 이상이 연속될 수 없으므로, k번 가장 큰 수를 더한 이후 1번은 두 번째 큰 수를 더해줘야 한다.
- 연산을 while루프당 한 번씩 해 주는 방식으로 처리할 수도 있지만, 효율적으로 계산하기 위해 수학적 아이디어를 사용할 수 있다.
- 가장 큰 수가 8, 두 번째로 큰 수가 6이라고 할 때, M이 8이고 K가 3이라면
- (8 + 8 + 8 + 6) + (8 + 8 + 8 + 6) 이 답이다.
- 8 8 8 6이라는 수열이 반복되는 것을 볼 수 있다.
- 이 수열이 등장하는 횟수를 찾으면, 계산을 간단히 처리할 수 있다.
- 수열의 크기는 k + 1이므로, 수열이 등장하는 횟수는 m / (k+1)이다.
- 그렇다면, 가장 큰 수가 등장하는 횟수는, 수열 등장 횟수 * k이다. k * (m / (k + 1))
- 만약, m이 k + 1로 나누어 떨어지지 않는 경우, 가장 큰 수는 M을 수열이 등장하는 횟수로 나누었을 때 나머지만큼 더 등장한다. m % (k + 1)
- 최종적으로, 가장 큰 수가 등장하는 횟수는 k * (m / (k + 1)) + m % (k + 1)
- 두 번째로 큰 숫자가 등장하는 횟수는 m 에서 가장 큰 수가 등장하는 횟수를 빼주면 된다.
2. 숫자 카드 게임
더보기// 그리디 알고리즘 >> p.96 숫자 카드 게임 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // 첫 작성 답안 { // int n, m, input, ans = 0; // cin >> n >> m; // // vector<vector<int>> cards(n); // for (int i = 0; i < n; ++i) // { // for (int j = 0; j < m; ++j) // { // cin >> input; // cards[i].push_back(input); // } // } // // 최소값이 가장 큰 행을 찾는다. // for (int i = 0; i < n; ++i) // { // sort(cards[i].begin(), cards[i].end()); // } // // // 각 행의 최소값을 비교한다. // for (int i = 0; i < n; ++i) // { // if (cards[i][0] > ans) // ans = cards[i][0]; // } // // cout << ans; } // 개선안 { int n, m, input; cin >> n >> m; int ans = 0; for (int i = 0; i < n; ++i) { // 한 줄씩 입력 받아서 행의 가장 작은 수 찾는다. int minVal = 10001; for (int j = 0; j < m; ++j) { cin >> input; minVal = min(minVal, input); } // 행의 최소값들을 비교해 가장 큰 수를 찾는다. ans = max(ans, minVal); } cout << ans; } return 0; }- 한 행 입력 당, 가장 작은 수를 찾고, 모든 행 중 작은 수 중 가장 큰 수를 찾으면 된다.
3. 1이 될 때까지
더보기// 그리디 알고리즘 >> p.99 1이 될 때까지 #include <iostream> using namespace std; int main() { int n, k, ans = 0; cin >> n >> k; // n 이 k 이상일 경우 계속 나눈다. while (n >= k) { // 나누어 떨어지는 경우 if (n % k == 0) { n /= k; ++ans; } // 나누어 떨어지지 않는 경우 배수가 되도록 뺀다. else { ans += n % k; n -= n % k; } } ans += n - 1; cout << ans; }- 나누기 연산을 가장 많이 하는 것이 최적해를 찾는 방법이다.
- 나누가 연산이 n을 가장 많이 감소시키고, n을 가장 적은 연산 횟수로 1로 만드는 것이 목적이므로
<이것이 취업을 위한 코딩 테스트다> 를 보고 정리한 자료입니다.