당장 좋은 것만 선택하는 그리디

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 자주 정렬 알고리즘과 짝을 이뤄 출제

예제: 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 해설

아이디어: 가장 큰 화폐 단위부터 돈을 거슬러 주는 것

답안

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, count = 0;
    cin >> n;
    
    int coinTypes[4] = {500, 100, 50, 10};
    for(int coin : coinTypes) {
    	count += n / coin;
        n %= coin;
    }
    
    cout << count;
    
    return 0;
}

시간 복잡도

화폐의 종류가 K개라고 할 때 위 코드의 시간 복잡도는 O(K)

그리디 알고리즘의 정당성

그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다.

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

어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.

실전 문제

큰 수의 법칙

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지 만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4+4+4+4+4+4+4인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

단순하게 푸는 답안

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> v;
	for(int i=0; i<n; i++){
	    int t;
	    cin >> t;
	    v.push_back(t);
	}
	
    sort(v.begin(), v.end());
    
    int sum=0;
    while(m > 0){
        sum += v.at(n-1) * k;
        m -= k;
        if(m == 0) break;
        
        sum += v.at(n-2);
        m -= 1;
        
        if(m<k) k = m;
    }
    
    cout << sum;
    
    return 0;
}

문제 해설

가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.
하지만 단순한 풀이는 M의 크기가 커진다면 시간 초과 판정을 받을 것이다.

먼저 반복되는 수열에 대해서 파악해야 한다.
가장 큰 수는 6, 두 번째로 큰 수는 5, M이 8, K가 3이라면 수열 {6, 6, 6, 5}가 반복된다.
그렇다면 반복되는 수열의 길이는 K+1이다. 따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.

이때 M이 (K+1)로 나누어떨어지지 않는 경우도 고려해야 한다. M을 (K+1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해진다. 즉, 가장 큰 수가 더해지는 횟수는 다음과 같다.
int(M / (K+1)) * K + M % (K+1)
두 번째로 작은 수는 M - (가장 큰 수가 더해지는 횟수) 이다.

답안

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m, k;
	vector<int> v;
	
	cin >> n >> m >> k;
	for(int i=0; i<n; i++){
	    int t;
	    cin >> t;
	    v.push_back(t);
	}
	
    sort(v.begin(), v.end());
    
    int count = (int)(m/(k+1))*k + m%(k+1);
    int sum = count * v.at(n-1) + (m-count) * v.at(n-2);
    
    cout << sum;
    
    return 0;
}

숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N × M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

예를 들어 3 × 3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.

3 1 2
4 1 4
2 2 2

여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다.

카드들이 N × M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

문제 해설

아이디어: 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것

내 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m, i, j, idx;
	cin >> n >> m;
	
	int** arr = new int* [n];
	for(i=0; i<n; i++){
	    arr[i] = new int[m];
	}
	
	for(i=0; i<n; i++){
	    for(j=0; j<m; j++){
	        int x;
	        cin >> x;
	        arr[i][j] = x;
	    }
	}
	
	for(i=0; i<n; i++){
	    sort(arr[i], arr[i]+m);
	}
	
	idx=0;
	for(i=0; i<n; i++){
	    if(arr[idx][0] <= arr[i][0]) idx = i;
	}
	
	cout << arr[idx][0];
    return 0;
}

교재 답안

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int result = 0;
    for (int i = 0; i < n; i++) {
        vector<int> data(m);
        for (int j = 0; j < m; ++j) {
            cin >> data[j];
        }
        // 현재 줄에서 가장 작은 수 찾기
        int min_value = *min_element(data.begin(), data.end());
        // 가장 작은 수들 중에서 가장 큰 수 찾기
        result = max(result, min_value);
    }

    cout << result;
    return 0;
}

정리

• 모든 값을 다 읽고 나서 크기를 비교할 필요가 없다.
  → 2차원 배열을 선언하지 않고, 한 줄 읽을 때마다 새로운 벡터/배열을 생성해도 된다.
• 최소값을 구할 때, sort() 함수를 사용한 후 첫 번째 요소를 가져와도 되지만, min_element 함수를 사용해도 된다.

1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

문제 해설

아이디어: 최대한 많이 나누기

N이 100억 이상의 큰 수가 되는 경우에도 빠르게 동작하려면, N이 K의 배수가 되도록 한 번에 빼는 방식으로 코드를 작성할 수 있다.

내 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k, count = 0;
	cin >> n >> k;
	
	while(n > 1) {
	    if(n % k == 0){
	        n /= k;
	        count++;
	    }
	    else {
	        n--;
	        count ++;
	    }
	}
	
	cout << count;
	
    return 0;
}

교재 답안

#include <bits/stdc++.h>

using namespace std;

int n, k;
int result;

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

    while (true) {
        // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
        int target = (n / k) * k;
        result += (n - target);
        n = target;
        // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if (n < k) break;
        // K로 나누기
        result += 1;
        n /= k;
    }

    // 마지막으로 남은 수에 대하여 1씩 빼기
    result += (n - 1);
    cout << result << '\n';
}