[이것이 취업을 위한 코딩 테스트다] Chapter 03 - 그리디(Greedy)

 

 

---

Chapter 03 - 그리디(Greedy)

 

1. 그리디 알고리즘(=탐욕법)

: 현재 상황에서 지금 당장 좋은 것 만 고르는 방법

👉 매 순간 좋아 보이는 것만 선택

👉 현재의 선택이 나중에 미칠 영향에 대해 고려X

 

 

예제 3-1 ) 거스름돈(C++)

Q .  손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다)

> 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함

#include <iostream>
using namespace std;

int n;//손님에게 받은 돈
int coin[4] = { 500, 100, 50, 10 };
int ans; //거스름돈의 개수
int main() {
    cin >> n;
    for (int i = 0; i < 4; i++) {
        ans += (n / coin[i]);
        n %= coin[i];
    }
    cout << ans;
}

- 시간복잡도 : 동전의 종류만큼 반복을 수행하므로, 동전의 종류가 k라 할때 O(k) 가 된다.

 

⚠️ 그리디 알고리즘으로 해법을 찾을 때는 그 해법이 정당한지 검토해야 한다.

> 위의 예시에서 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전을 종합해 다른 해가 나올 수 없기 때문에 그리디로 해결이 가능함.

 

 

2. 실전문제 - 큰 수의 법칙(C++)

Q . 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만들어야 함

    단, 특정 인젝스에 해당하는 수가 연속으로 k번 초과해서 더해질 수 없음.

> 해결 알고리즘 : 제일 큰 수와 k를 초과하지 않을만큼 더하고 두번째 큰 수를 한 번 더하면서 m만큼 더해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k, ans;
int arr[1001];
int main() {
    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 (true) {
        if (m == 0) break;
        for (int i = 0; i < k; i++) {
            ans += big1;
            m--;
            if (m == 0) break;
        }
        ans += big2;
        m--;
    }
    
    cout << ans;    
}

> 이 방법은 m이 10,000 이하이므로 해결이 가능하지만, 500만이 넘는다면 시간 초과 이다. (시간복잡도 O(NlogN))

• O(1)
• O(logN) - O(N) : 1억
• O(NlogN): 5백만
• O(N^2) : 1만
• O(N^3) : 500
• O(2^N) : 20
• O(N!): 10

👉 반복되는 수열에 대해 파악하여 해결이 가능하다.

- 가장 큰 수가 더해지는 횟수 = (M/(K+1)) * K+ M%(K+1)

- 두 번째 큰 수가 더해지는 횟수 = M - ((M/(K+1)) * K+ M%(K+1))

 

 

3. 실전문제 - 숫자 카드 게임(C++)

Q . 책 96p 참조 

A . 각 행마다 가장 작은 수를 찾고 그 수 중에서 가장 큰 수를 찾으면 되는 문제

#include <iostream>
using namespace std;

int n, m;
int big = 10001;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int small = 0;
		for (int j = 0; j < m; j++) {
			int num;
			cin >> num;
			small = min(small, num);
		}
		big = max(big, small);
	}
	cout << big;
}

 

 

4. 실전문제 - 1이 될 때까지(C++)

Q . 어떠한 수가 1이 될 때까지 2가지 연산이 가능하다. 2가지 연산을 하여 1이 되는 최소의 연산의 수는 ?

     ⓐ N에서 1을 뺀다.

     ⓑ N에서 K로 나눈다.

A1 . 반대로 생각하여 1부터 시작해 1을 더하거나 K를 곱하여 N이 되는 최소의 연산의 수를 구하면 된다.

#include <iostream>
using namespace std;

int n, k, ans;
int main() {
	cin >> n >> k;

	int num = 1;
	while (true) {
		if (num == n) break;
		if (num * k <= n) {
			num *= k;
			ans++;
		}
		else {
			num++;
			ans++;
		}
	}
	cout << ans;
}

시간 복잡도는 최악의 경우가 1만 빼는 경우이므로 O(n) 이 된다. 따라서 n이 1억을 초과하면 시간초과 난다.

 

A2 . N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 작성 가능