지난 시간 복습

  • 동적 계획법: 답을 구하기 위해 부분 문제의 답을 이용하여 효율적으로 정답을 계산하는 알고리즘 설계 기법
  • 값을 저장한 뒤 재사용하는 방법을 이용하여 더욱 빠르게 정답을 구할 수 있었습니다.
  • Top-down 방식과 Bottom-up 방식에 대해서 학습하고, 각각의 구현 방법을 배웠습니다.
  • 동전 문제, 피보나치 함수 등 다양한 동적 계획법 문제를 풀어보았습니다.

오늘의 학습 목표

  1. 그리디 알고리즘에 대해 이해하기
  2. 그리디 알고리즘 관련 문제를 풀어보기

그리디 알고리즘의 개념

현재 상황에서 가장 최선의 선택을 고르는 알고리즘

그리디 알고리즘은 현재 상황에서 가장 최선의 선택을 고르는 알고리즘입니다. 이는 최적 부분 구조와 탐욕 선택 속성을 기반으로 합니다.

최적 부분 구조

최적 부분 구조는 각 부분 문제의 답을 알 때, 전체 문제의 답을 쉽게 구할 수 있는 특성입니다. 즉, 작은 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구할 수 있습니다.

탐욕 선택 속성

탐욕 선택 속성은 각 단계에서 가장 최선의 선택을 하는 것이 전체적으로 최적의 해를 구하는 방법이라는 속성입니다. 즉, 각 단계에서 지금 당장 최적인 선택을 하면서 최종적으로 전체적으로 최적의 해를 얻을 수 있습니다.

그리디 알고리즘은 이러한 최적 부분 구조와 탐욕 선택 속성을 이용하여 문제를 해결합니다. 각 단계에서 최선의 선택을 하면서 전체적으로 최적의 해를 찾아내는 효율적인 알고리즘입니다.

그러면 최선의 선택이란 무엇이고, 현재 상황에서 최선의 선택을 한다는 것은 무엇일까요? 문제를 살펴봅시다.

그리디 알고리즘 문제 예시

BOJ 30700번 KOREA 문자열 만들기

영어 대문자 K, O, R, E, A로만 이루어진 문자열 S에서 0개 이상의 문자를 지웠을 때 K로 시작하고 K, O, R, E, A 순서로 반복되는 문자열을 만드려고 할 때, 만들 수 있는 가장 긴 문자열을 구하여라.

해설

다음과 같이 문제를 풀어볼 수 있습니다.

  1. 부분 문제 정의:
    문자열 S의 부분 문자열을 고려하여 문제를 해결합니다. 여기서 부분 문자열은 문자열의 일부분을 의미하며, 문자열 S를 0개 이상의 문자를 삭제하면서 K, O, R, E, A 순서대로 반복되는 문자열을 만들어야 합니다.

  2. 최적 부분 구조:
    이 문제는 최적 부분 구조를 갖습니다. 주어진 문자열 S의 일부분에서 최대 길이의 반복 패턴을 찾아야 하므로, 작은 부분 문자열의 최적해를 이용하여 전체 문자열의 최적해를 구할 수 있습니다.

  3. 탐욕 선택 속성:
    문자열을 탐색할 때, K, O, R, E, A 순서대로 부분 문자열을 구성하기 위해 탐욕적으로 문자를 선택할 수 있습니다. 예를 들어, 현재 문자열에서 다음으로 나올 문자가 K이면 선택하고, 그 다음은 O, R, E, A 순서대로 선택해 나가면서 가장 긴 반복 패턴을 만들어 갈 수 있습니다.

해결 과정: 문자열 S를 순차적으로 탐색하면서 다음의 과정을 수행합니다:

K를 찾고, 그 다음 O, R, E, A 순서대로 문자를 찾아 반복 패턴을 구성합니다. 이러한 과정을 통해 만들어진 가장 긴 반복 패턴의 길이를 구합니다. 예를 들어, 문자열 “KOREAKOREAOKOAKOK”에서는 “KOREA”가 반복 패턴이므로 이를 찾아내어 가장 긴 패턴을 구할 수 있습니다.

이를 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    string s;
    cin >> s;

    string kor = "KOREA";
    ll ans = 0;
    for (auto a : s) {
        if (a == kor[ans % 5]) ans++;
    }

    cout << ans;
}

동전 거스름돈 문제

BOJ 11047 동전 0

해설

주어진 동전들의 종류와 거스름돈의 금액이 있을 때, 거스름돈을 주는데 필요한 동전의 최소 개수를 찾는 문제입니다. 그리디 알고리즘은 가장 큰 동전부터 최대한 많이 사용하는 방식으로 거스름돈을 주는 방법을 찾습니다.

이를 파이썬 코드를 통해 구현하면 다음과 같습니다.

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount >= coin:
            count += amount // coin
            amount %= coin
    return count

동전 거스름돈 문제의 최적 부분 구조와 탐욕 선택 속성에 대해서 설명해드리겠습니다.

1. 최적 부분 구조 (Optimal Substructure):
동전 거스름돈 문제는 최적 부분 구조를 갖습니다. 이는 큰 문제(거스름돈을 주는데 필요한 최소 동전 수)를 작은 문제(부분 문제들)로 분해할 수 있고, 작은 문제의 최적해를 이용하여 전체 문제의 최적해를 구할 수 있는 성질을 의미합니다. 예를 들어, 거스름돈 문제에서 거스름돈을 주는데 필요한 최소 동전 수를 구하는 것은 각 동전의 선택에 따라 하위 문제로 나눌 수 있습니다.

다음 예시를 같이 살펴보겠습니다. 거스름돈 문제를 1원, 5원, 10원, 50원, 100원, 500원 동전을 사용하여 최소 동전 수로 구성하는 예시를 각 경우에 따라 살펴보겠습니다.

  1. 500원 동전만을 이용하여 1743원 거스름돈을 구하는 경우:

500원 동전을 최대한 사용하여 거스름돈을 구성합니다. 500원으로는 1743원을 정확히 나눌 수 없으므로, 500원 동전 3개(1500원)와 나머지 243원을 구성해야 합니다. 따라서 최소 동전 수는 3개(500원 동전 3개)입니다.

  1. 100원, 500원 동전만을 이용하여 1743원 거스름돈을 구하는 경우:

100원과 500원 동전을 사용하여 거스름돈을 구성합니다. 먼저 500원 동전 3개(1500원)를 사용합니다. 남은 금액은 243원이 남습니다. 이를 100원 동전 2개로 구성할 수 있습니다. 따라서 최소 동전 수는 5개(500원 동전 3개 + 100원 동전 2개)입니다.

  1. 50원, 100원, 500원 동전만을 이용하여 1743원 거스름돈을 구하는 경우:

50원, 100원, 500원 동전을 사용하여 거스름돈을 구성합니다. 먼저 500원 동전 3개(1500원)를 사용합니다. 남은 금액은 243원이 남습니다. 이를 100원 동전 2개와 50원 동전 1개로 구성할 수 있습니다. 따라서 최소 동전 수는 6개(500원 동전 3개 + 100원 동전 2개 + 50원 동전 1개)입니다.

  1. 10원, 50원, 100원, 500원 동전만을 이용하여 1743원 거스름돈을 구하는 경우:

10원, 50원, 100원, 500원 동전을 사용하여 거스름돈을 구성합니다. 먼저 500원 동전 3개(1500원)를 사용합니다. 남은 금액은 243원이 남습니다. 이를 100원 동전 2개, 10원 동전 4개로 구성할 수 있습니다. 따라서 최소 동전 수는 9개(500원 동전 3개 + 100원 동전 2개 + 10원 동전 4개)입니다.

이 과정을 반복하여 5원, 1원 동전까지 같은 과정을 수행하면 거스름돈의 동전의 최소 개수를 구할 수 있습니다.

이렇게 동전의 조합에 따라 최소 동전 수로 1743원을 구성하는 과정을 살펴볼 수 있습니다.

2. 탐욕 선택 속성 (Greedy Choice Property):
동전 거스름돈 문제의 탐욕 선택 속성은 각 단계에서 현재 상황에서 가장 최적인 선택을 하는 것이 전체 문제의 최적해를 찾을 수 있다는 것을 의미합니다. 즉, 각 단계에서 가장 큰 동전부터 최대한 많이 선택함으로써 최적해에 도달할 수 있습니다. 탐욕 알고리즘이 항상 최적해를 보장하는 이유는 각 단계에서 탐욕적으로 선택한 결과가 전체적으로 최적해와 일치하기 때문입니다.

동전 가치의 배수 관계 여부에 따른 경우 분류:

  • 모든 동전의 가치가 배수 관계를 만족하는 경우: 이 경우에는 탐욕 알고리즘이 항상 최적해를 구할 수 있습니다. 왜냐하면 가장 큰 동전부터 시작하여 최대한 많이 선택하면 되기 때문입니다. 예를 들어, 동전의 가치가 1원, 5원, 10원, 50원, 100원, 500원처럼 배수 관계에 있는 경우에는 탐욕 알고리즘이 항상 최적 동전 구성을 찾을 수 있습니다.

  • 동전의 가치가 배수 관계를 만족하지 않는 경우: 이 경우에는 탐욕 알고리즘이 항상 최적해를 보장하지 않습니다. 예를 들어, 동전의 가치가 1원, 3원, 4원처럼 배수 관계가 아닌 경우에는 탐욕 알고리즘이 최적해를 찾지 못할 수 있습니다. 이러한 경우에는 다이나믹 프로그래밍 등 다른 방법을 사용하여 최적해를 구해야 할 수 있습니다.

관련 문제: BOJ 11047 동전 0

작업 스케쥴링 문제

BOJ 1931 회의실 배정

앞서 살펴보았던 KOREA 문자열 만들기에서 얻었던 아이디어와 비슷한 방식으로 문제를 해결할 수 있습니다. 한 번 문제를 푸는 시간을 가져봅시다.

해설

다음과 같은 아이디어를 떠올릴 수 있어야 합니다.

가능한 회의 중에서 가장 빨리 끝나는 회의를 진행해야 한다.

정당성 증명은 다음과 같습니다.
임의의 두 회의 시간 $(s_1, e_1), (s_2, e_2) (e_1 < e_2)$가 있다고 합시다. 그리고 회의의 총 시간이 $T$라고 합시다. 첫 번째 회의를 선택하는 경우 남은 시간은 $T-e_1$, 두 번째 회의를 선택하는 경우 남은 시간은 $T-e_2$가 됩니다. 이 경우 $T-e_1 > T-e_2$이므로 회의가 끝나는 시간이 먼저인 것을 선택하는 것이 무조건 이득입니다.

아래의 코드는 회의실 배정 문제를 C++로 구현한 것입니다. 이 문제는 그리디 알고리즘을 활용하여 최대한 많은 회의를 진행할 수 있는 방법을 찾는 문제입니다. 코드를 통해 해결 과정을 설명하겠습니다.

  1. 구조체 정의 및 우선순위 큐 설정:
    먼저 meeting_time 구조체를 정의하여 각 회의의 시작 시간(start)과 끝 시간(end)을 저장합니다. 그리고 cmp 구조체를 정의하여 우선순위 큐(priority_queue)에서 회의를 정렬할 기준을 설정합니다. 여기서는 끝나는 시간(end)이 빠른 순서대로 정렬하며, 끝나는 시간이 같다면 시작 시간(start)이 더 늦은 순서로 정렬합니다.

  2. 입력 받기 및 회의 정보 저장:
    priority_queue를 이용하여 회의 정보를 저장합니다. 각 회의의 시작 시간과 끝 시간을 입력 받고, pq.push({tmp1, tmp2})를 통해 우선순위 큐에 회의 정보를 추가합니다.

  3. 그리디 알고리즘을 통한 회의실 배정:
    우선순위 큐에서 회의를 하나씩 꺼내면서 최대한 많은 회의를 선택합니다. current_end 변수를 사용하여 현재 진행 중인 회의의 끝나는 시간을 관리합니다. 우선순위 큐에서 꺼낸 회의의 시작 시간이 current_end보다 크거나 같다면 해당 회의를 선택하고 current_end를 해당 회의의 끝 시간으로 업데이트합니다. 선택한 회의 수(ans)를 증가시킵니다.

  4. 선택된 회의 수 출력:
    모든 회의를 확인한 후 선택된 회의 수(ans)를 출력합니다. 이 값은 최대로 진행할 수 있는 회의의 수를 나타냅니다.

이렇게 그리디 알고리즘을 활용하여 회의실 배정 문제를 해결할 수 있습니다. 이 코드는 끝나는 시간이 빠른 순서대로 회의를 선택하여 최대한 많은 회의를 진행하도록 합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct meeting_time{
    int start;
    int end;
};

struct cmp{
    bool operator()(meeting_time a, meeting_time b){
        if (a.end == b.end) {
            return a.start > b.start;
        }
        return a.end > b.end;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    
    priority_queue<meeting_time, vector<meeting_time>, cmp> pq;
    int n, i, tmp1, tmp2, ans = 0;
    cin >> n;

    for (i = 0; i < n; i++) {
        cin >> tmp1 >> tmp2;
        pq.push({tmp1, tmp2});
    }

    int current_end = 0;
    while (!pq.empty()) {
        tmp1 = pq.top().start;
        tmp2 = pq.top().end;

        if (tmp1 < current_end) {
            pq.pop();
            continue;
        }

        current_end = tmp2;
        ans++;
        pq.pop();
    }

    cout << ans;
}

정리

그리디 알고리즘은 각 단계에서 현재 상황에서 가장 최적의 선택을 하면서 전체적으로 최적의 해를 찾는 알고리즘입니다. 이 알고리즘은 최적 부분 구조와 탐욕 선택 속성을 이용하여 문제를 해결합니다.

  • 최적 부분 구조 (Optimal Substructure):
    작은 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구할 수 있는 특성을 의미합니다. 작은 부분 문제의 해를 조합하여 전체 문제의 해를 구하는 방식으로 문제를 해결할 수 있습니다.

  • 탐욕 선택 속성 (Greedy Choice Property):
    각 단계에서 가장 최적의 선택을 하면서 전체적으로 최적의 해를 찾을 수 있다는 속성을 의미합니다. 각 단계에서 가장 최적인 선택을 하면서 최종적으로 전체적으로 최적의 해를 찾는 것이 가능합니다.

그리디 알고리즘은 이러한 특성을 활용하여 다양한 문제를 효율적으로 해결할 수 있습니다. 예를 들어, 동전 거스름돈 문제나 회의실 배정 문제 등이 그리디 알고리즘을 적용할 수 있는 대표적인 예시입니다.

이러한 알고리즘을 사용할 때는 주어진 문제의 특성을 잘 파악하고, 각 단계에서의 최적 선택을 결정하는 기준을 명확히 정의해야 합니다. 그리디 알고리즘은 항상 최적해를 보장하는 것은 아니지만, 많은 경우에 효율적으로 최적해에 가까운 해를 구할 수 있는 강력한 알고리즘입니다.

PS에서는 그리디 알고리즘을 이용해서 더 빠른 시간 안에 문제를 풀 수 있는 방법을 찾고, 최적해가 해임을 보장하는 경우에 대한 증명을 하는 방식으로 더 빠르게 문제를 풀 수 있습니다. 이러한 증명, 문제풀이 연습을 통해 백준 티어를 더 많이 올릴 수 있을 것입니다!