그리디 - 지금 최선이 전체 최선일 때

이 장에서 배우는 것

앞 장에서 구간을 움직이며 필요한 정보를 유지했다면, 이번에는 여러 후보 중 무엇을 먼저 선택할지 결정한다. 선택한 뒤 되돌아가지 않아도 좋은 답을 얻는 방법을 그리디(greedy) 알고리즘이라 한다. 다만 눈앞에서 좋아 보인다는 이유만으로 선택을 확정할 수는 없다. 지금의 선택이 남은 선택을 얼마나 제한하는지 살피고, 최적해의 일부를 바꾸어도 결과가 나빠지지 않는다는 근거가 필요하다.

이 장에서는 한 공간에서 진행할 일정을 최대한 많이 고른다. 가장 빨리 끝나는 일정부터 고르는 규칙을 손으로 따라가고, 그 선택을 최적해 안으로 옮겨 넣는 교환 논증을 만든다. 이어서 그럴듯하지만 틀린 선택 기준과, 목표가 바뀌어 더는 성립하지 않는 기준을 구분한다.

• 일정 선택 문제에서 가능 조건과 최대화할 대상을 분리한다.
• 가장 빨리 끝나는 일정이 남은 선택에 유리한 이유를 설명한다.
• 교환 논증과 반복 중 불변식으로 알고리즘의 정당성을 보인다.
• 작은 반례를 만들어 잘못된 그리디 규칙을 검토한다.
• 빠른 풀이를 구현하고 작은 입력의 모든 부분집합을 조사하는 풀이와 대조한다.

문제 상황

작은 공유 작업실에 예약 요청이 들어온다. 작업실은 하나이며, 한 번에 하나의 요청만 받을 수 있다. 요청마다 이름, 시작 시각, 종료 시각이 있다. 운영자는 가능한 한 많은 요청을 승인하려 한다. 각 요청을 승인했을 때의 가치는 같고, 요청을 나누어 일부 시간만 승인할 수는 없다.

시각은 같은 날의 기준 시점부터 센 정수 단위로 표시한다. 일정의 구간은 시작 시각을 포함하고 종료 시각은 포함하지 않는 반열린 구간 [시작, 종료)로 해석한다. 따라서 어떤 일정이 4에 끝나고 다음 일정이 4에 시작하면 함께 승인할 수 있다. 정리 시간은 없으며, 모든 요청은 시작 시각이 종료 시각보다 작다.

첫 번째 문제는 다음 다섯 요청에서 승인할 수 있는 최대 개수를 구하는 것이다. 이름은 요청을 구별하기 위한 표시이며 선택의 가치를 나타내지 않는다. 입력에 적힌 순서는 예약 우선순위가 아니다.

작업실의 예약 요청과 사용 시간

이름	시작	종료	사용 길이
가	0	4	4
나	1	2	1
다	2	3	1
라	3	5	2
마	4	6	2

여기서 출력해야 할 핵심은 최대 개수다. 실제 승인 목록도 함께 구하면 선택 과정이 제대로 작동했는지 확인하기 쉽다. 가능한 최적 목록이 여러 개라면 그중 하나를 출력한다. 모든 최적 목록을 출력하라는 요구와는 다르다.

현실의 예약 시스템에는 우선 고객, 준비 시간, 공간별 장비 같은 조건이 추가될 수 있다. 지금의 문제에서는 그런 조건을 넣지 않는다. 조건을 명확히 제한해야 선택 기준을 증명할 수 있다. 뒤에서 조건을 바꾼 짧은 문제를 통해 이 제한이 왜 필요한지도 확인한다.

가장 빨리 끝나는 일정을 먼저 고른다

일정을 하나 승인하면 그 일정과 겹치는 요청은 승인할 수 없다. 그렇다면 현재 승인할 수 있는 요청 중 가장 빨리 끝나는 것을 골라 작업실을 일찍 비우는 방법을 생각할 수 있다. 시작이 빠르다는 사실보다 종료가 빠르다는 사실이 다음 일정에 직접 영향을 준다.

모든 요청을 종료 시각의 오름차순으로 정렬한다. 선택한 마지막 일정의 종료 시각을 기억하며 정렬된 목록을 한 번 훑는다. 아직 아무것도 고르지 않았거나, 현재 요청의 시작이 마지막 종료 이상이면 승인한다. 시작이 마지막 종료보다 작으면 건너뛴다.

종료 시각이 같다면 어느 요청을 먼저 골라도 개수의 최댓값에는 영향이 없다. 이후에 사용할 수 있는 시간이 같기 때문이다. 구현에서는 시작 시각과 이름까지 정렬 기준에 넣어 동률의 처리 순서를 일정하게 만든다. 이는 출력의 재현성을 위한 규칙이다.

종료 시각 순서로 훑으며 승인 여부를 결정하는 과정

요청	검사 직전 마지막 종료	판단	검사 후 승인 목록
나 [1, 2)	없음	첫 요청이므로 승인	나
다 [2, 3)	2	2 이상에서 시작하므로 승인	나, 다
가 [0, 4)	3	3보다 먼저 시작하므로 제외	나, 다
라 [3, 5)	3	3 이상에서 시작하므로 승인	나, 다, 라
마 [4, 6)	5	5보다 먼저 시작하므로 제외	나, 다, 라

이 규칙은 가능한 요청을 볼 때마다 선택을 확정한다. 나를 승인한 뒤 가를 만나더라도 나를 취소하고 가를 넣어 보지 않는다. 그리디의 장점은 이런 단순함에 있지만, 그만큼 되돌아갈 필요가 없다는 증명이 중요하다.

또한 요청을 건너뛴다는 판단과, 그 요청을 어떤 경우에도 사용할 수 없다는 판단은 다르다. 가는 나와 다를 승인한 현재 목록에는 들어갈 수 없다. 하지만 처음부터 가를 선택하는 다른 목록은 존재한다. 우리가 보여야 할 것은 모든 가능한 목록을 보존한다는 사실이 아니라, 최적 개수를 얻을 가능성을 보존한다는 사실이다.

교환 논증으로 선택을 정당화한다

교환 논증(exchange argument)은 어떤 최적해가 있다고 놓고, 그 안의 선택을 우리가 원하는 선택으로 바꾸는 방법이다. 바꾼 뒤에도 조건을 만족하고 목적값이 줄지 않는다면, 그리디 선택을 포함하는 최적해도 존재한다고 말할 수 있다.

아직 아무 일정도 고르지 않은 상황을 생각한다. 가장 빨리 끝나는 요청을 g라 하자. 요청이 하나 이상이면 최적 목록도 적어도 하나를 포함한다. 어떤 최적 목록의 첫 요청을 o라 하고, 그 목록을 실제 진행 순서대로 나열한다.

1. g는 모든 요청 중 가장 빨리 끝나므로 g의 종료는 o의 종료 이하이다.
2. 최적 목록에서 o 다음에 오는 모든 요청은 o의 종료 이상에서 시작한다.
3. 따라서 그 요청들은 g의 종료 이상에서도 시작한다. o를 g로 바꿔도 뒤의 요청과 겹치지 않는다.
4. 요청 하나를 다른 요청 하나로 바꾸었으므로 승인 개수는 그대로다. g로 시작하는 최적 목록을 얻는다.

g의 시작이 o의 시작보다 늦어도 문제없다. 첫 선택 앞에는 보존해야 할 일정이 없고, 뒤의 요청에 영향을 주는 경계는 종료 시각이다. 양의 길이를 가진 요청만 허용했으므로 g가 원래 목록의 뒤쪽 요청과 같은 요청일 수도 없다. 뒤쪽 요청은 o가 끝난 뒤에 시작하고 그보다 더 늦게 끝나기 때문이다.

이제 g가 끝난 뒤 시작하는 요청만 남긴다. 남은 요청에서도 가능한 한 많이 고르는 문제는 원래 문제와 같은 모양이다. 남은 요청으로 더 많은 일정을 고를 수 있는데도 적게 고르면, g 뒤에 그 더 좋은 목록을 붙여 전체 최적값을 늘릴 수 있다. 따라서 전체 최적 목록의 나머지 부분도 남은 문제에서 최적이어야 한다.

같은 논리를 두 번째 선택, 세 번째 선택에 반복할 수 있다. 이미 선택한 일정 뒤에서 가능한 요청 중 종료가 가장 빠른 것을 고르면, 그 요청을 포함하는 최적 연장 목록이 존재한다. 요청이 없을 때는 빈 목록이 최적이므로 반복의 끝도 성립한다. 이것이 선택을 되돌리지 않아도 되는 이유다.

반복문이 유지하는 사실

구현을 읽을 때는 두 가지 사실을 함께 보면 된다. 첫째, 지금까지 선택한 요청은 서로 겹치지 않으며 마지막 종료 시각은 그 목록의 끝이다. 둘째, 지금까지 확정한 선택을 앞부분으로 갖는 전체 최적 목록이 적어도 하나 존재한다. 첫째는 결과의 가능성을, 둘째는 최적값을 잃지 않았음을 나타낸다.

현재 요청이 마지막 종료 전에 시작하면 지금의 선택 뒤에 붙일 수 없으므로 건너뛴다. 붙일 수 있는 요청을 만나면 정렬 순서상 남은 후보 중 종료가 가장 빠르다. 교환 논증에 따라 그 요청을 선택해도 두 번째 사실을 유지한다. 목록을 모두 확인한 뒤에는 더 붙일 요청이 없으므로 현재 목록 자체가 최적 목록이 된다.

시간과 공간을 센다

요청 수를 n이라 하자. 정렬에는 O(n log n) 시간이 들고, 정렬된 목록을 한 번 훑는 데 O(n) 시간이 든다. 따라서 전체 시간 복잡도는 O(n log n)이다. 비어 있거나 하나뿐인 입력은 상수 시간에 처리되며, 이 표기는 요청 수가 커질 때의 증가를 설명한다.

완성 코드에서는 원본 순서를 보존하려고 sorted로 새 목록을 만든다. 정렬한 목록과 선택 결과를 저장하므로 추가 공간은 O(n)이다. 마지막 종료를 저장하는 변수만 보면 O(1)이지만, 그것을 전체 함수의 공간 복잡도라고 적으면 새 목록의 비용을 빠뜨린다.

그럴듯한 규칙을 반례로 점검한다

그리디를 떠올렸다면 성공하는 예를 여러 개 보는 것보다 선택이 불리해질 만한 작은 입력을 만드는 편이 유용하다. 반례 하나면 규칙이 항상 맞는다는 주장을 부정할 수 있다. 반대로 반례를 찾지 못했다는 사실만으로 규칙이 증명되지는 않는다.

짧은 점검을 먼저 처리하면 어떨까

두 번째 문제는 점검 공간 하나에 들어온 작업을 최대한 많이 처리하는 것이다. 요청은 가 [0, 3), 나 [3, 6), 다 [2, 4)다. 각 요청의 길이는 차례로 3, 3, 2다. 공간 사용 조건과 목표는 작업실 문제와 같고, 여기서는 가장 짧은 작업을 먼저 확정하는 규칙을 시험한다.

길이가 가장 짧은 다를 선택하면 가와 나가 모두 겹쳐서 더 고를 수 없다. 결과는 1개다. 하지만 가 다음에 나를 선택하면 2개를 처리할 수 있다. 짧은 작업도 시간대의 가운데를 차지하면 양쪽의 긴 작업을 모두 막을 수 있다. 사용 길이와 다음 요청을 허용하는 종료 경계는 서로 다른 정보다.

가장 일찍 시작하는 요청을 고르는 규칙도 일반적으로 맞지 않는다. 첫 번째 작업실 예에서 가장 일찍 시작하는 가를 고르면 그 뒤에 마를 붙여 2개를 승인한다. 반면 종료가 빠른 순서로는 나, 다, 라의 3개를 승인한다. 시작이 빠르다는 이유만으로 다음 선택의 여유가 커지지는 않는다.

승인 개수 대신 적립 점수를 더하면 어떨까

세 번째 문제는 행사 공간의 예약 점수 합계를 최대화하는 것이다. 요청은 가 [0, 2), 점수 3과 나 [2, 4), 점수 3, 다 [0, 4), 점수 8이다. 겹침 조건은 같지만 목표가 승인 개수에서 점수 합계로 바뀌었다.

종료가 빠른 순서로 선택하면 가와 나를 승인하여 점수 6을 얻는다. 다 하나를 승인하면 점수 8이다. 앞에서 증명한 교환은 요청 개수를 보존했을 뿐, 점수 합계를 보존하지 않는다. 최적 목록의 첫 요청을 다른 요청으로 바꾸는 순간 점수가 줄어들 수 있으므로 같은 증명을 사용할 수 없다.

점수 문제를 여기서 다른 알고리즘으로 풀지는 않는다. 중요한 일은 조건이나 목표가 달라졌을 때 기존 규칙을 그대로 적용하지 않는 것이다. 무엇을 최대로 만드는지, 교환할 때 그 값이 유지되는지, 뒤의 선택을 정말 보존할 수 있는지를 다시 물어야 한다.

완성 코드

다음 프로그램을 main.py로 저장한다. 예시 입력은 문자열에 두고 io.StringIO로 읽는다. 첫 줄은 요청 수이고, 이어지는 줄은 이름, 시작, 종료다. 이름은 공백을 포함하지 않는 고유한 표시로 가정한다. 프로그램은 예시의 승인 목록을 출력한 뒤 작은 입력 전수 대조를 수행하고 종료한다.

검증에는 두 겹의 전체 조사를 사용한다. 먼저 0부터 4까지의 정수 시각으로 만들 수 있는 양의 길이 구간 10개를 준비하고, 이 구간들의 모든 부분집합 1,024개를 입력으로 만든다. 그런 다음 각 입력 안에서 다시 모든 선택 부분집합을 조사하여 최적 개수를 계산한다. 빠른 풀이와 느린 풀이가 같은 개수를 내는지 비교한다.

import io
from itertools import combinations


EXAMPLE = """5
가 0 4
나 1 2
다 2 3
라 3 5
마 4 6
"""


def read_requests(text):
    stream = io.StringIO(text)
    count = int(stream.readline())
    requests = []
    for _ in range(count):
        name, start, end = stream.readline().split()
        start, end = int(start), int(end)
        if start >= end:
            raise ValueError("시작은 종료보다 작아야 한다")
        requests.append((name, start, end))
    return requests


def choose_greedy(requests):
    ordered = sorted(
        requests,
        key=lambda request: (request[2], request[1], request[0]),
    )
    chosen = []
    last_end = None
    for request in ordered:
        name, start, end = request
        if last_end is None or start >= last_end:
            chosen.append(request)
            last_end = end
    return chosen


def is_compatible(requests):
    for left, right in combinations(requests, 2):
        separated = left[2] <= right[1] or right[2] <= left[1]
        if not separated:
            return False
    return True


def best_count_exhaustive(requests):
    best = 0
    for mask in range(1 << len(requests)):
        subset = [
            request
            for index, request in enumerate(requests)
            if mask & (1 << index)
        ]
        if is_compatible(subset):
            best = max(best, len(subset))
    return best


def verify_all_small_inputs():
    universe = []
    for start in range(4):
        for end in range(start + 1, 5):
            name = f"구간{len(universe)}"
            universe.append((name, start, end))

    checked = 0
    for mask in range(1 << len(universe)):
        requests = [
            request
            for index, request in enumerate(universe)
            if mask & (1 << index)
        ]
        chosen = choose_greedy(requests)
        expected = best_count_exhaustive(requests)
        if not is_compatible(chosen) or len(chosen) != expected:
            raise AssertionError(
                f"대조 실패: 입력={requests}, 선택={chosen}, 정답={expected}"
            )
        checked += 1
    return checked


def main():
    requests = read_requests(EXAMPLE)
    chosen = choose_greedy(requests)
    print("선택:", ", ".join(name for name, _, _ in chosen))
    print("최대 개수:", len(chosen))
    checked = verify_all_small_inputs()
    print(f"작은 입력 전수 대조: {checked}개 통과")


if __name__ == "__main__":
    main()

줄별 해설

import와 EXAMPLE. io는 문자열을 파일처럼 읽기 위해 사용한다. combinations는 목록에서 서로 다른 두 요청을 뽑아 모든 쌍을 검사하는 데 사용한다. EXAMPLE은 줄바꿈을 포함한 입력 문자열이다. 입력을 기다리는 호출이나 난수 생성이 없으므로 실행할 때마다 같은 데이터를 같은 순서로 검사한다.

read_requests의 입력 처리. io.StringIO(text)가 읽기 위치를 가진 객체를 만든다. 첫 readline은 요청 수를 읽고, 반복문 안의 readline은 요청 한 줄을 읽는다. split으로 세 항목을 나누고 시각을 정수로 바꾼다. 시작이 종료 이상이면 이 장에서 정한 입력 조건에 어긋나므로 예외를 발생시킨다. 각 요청은 (이름, 시작, 종료) 순서의 튜플로 저장한다.

choose_greedy의 정렬. request[2]가 종료, request[1]이 시작, request[0]이 이름이다. 정렬 기준에 튜플을 사용하면 종료를 먼저 비교하고, 같을 때 시작을 비교하며, 둘 다 같으면 이름을 비교한다. 원본 요청 목록은 수정하지 않는다.

chosen과 last_end. chosen은 승인한 요청 목록이다. last_end의 None은 아직 선택한 요청이 없다는 뜻이다. 임의의 숫자를 초기 경계로 사용하지 않으므로 음수 시각을 가진 요청이 함수에 전달되어도 첫 선택을 잘못 거르지 않는다. 조건문의 or는 왼쪽이 참이면 오른쪽을 평가하지 않으므로 None과 정수를 비교하지 않는다.

승인 조건과 갱신. start가 last_end 이상이면 요청을 chosen에 넣고 종료 경계를 end로 바꾼다. 승인하지 않은 요청의 종료는 경계에 반영하지 않는다. 함수는 개수만 반환하는 대신 목록을 반환한다. 이 덕분에 출력과 검증에서 같은 선택 결과를 사용할 수 있다.

is_compatible의 쌍 검사. 두 요청이 겹치지 않으려면 왼쪽 요청이 끝난 뒤 오른쪽 요청이 시작하거나, 그 반대여야 한다. 이 두 조건을 or로 연결한다. 겹치는 쌍을 하나라도 찾으면 False를 반환하고, 끝까지 없으면 True를 반환한다. 빈 목록이나 하나뿐인 목록에는 검사할 쌍이 없으므로 True가 된다.

best_count_exhaustive의 선택 표현. 요청이 n개이면 각 요청을 고르거나 고르지 않는 경우는 2의 n제곱 개다. 1 << n은 이 개수를 만든다. mask의 index번째 이진 자릿값이 1이면 해당 요청을 subset에 넣는다. mask가 0인 경우 빈 선택도 검사하므로 빈 입력을 따로 처리할 필요가 없다.

느린 정답의 갱신. 부분집합이 모든 쌍의 겹침 검사를 통과했을 때만 개수를 비교한다. 이 풀이는 종료가 빠른 것을 먼저 골라야 한다는 가정을 사용하지 않는다. 가능한 선택을 모두 확인하므로 최적 개수를 놓치지 않는다. 한 입력에 요청이 n개 있을 때 시간은 O(2의 n제곱 × n제곱), 추가 공간은 O(n)이다.

verify_all_small_inputs의 입력 생성. start를 0, 1, 2, 3으로 순회하고 end를 start보다 큰 값부터 4까지 순회한다. 구간 수는 4 + 3 + 2 + 1 = 10개다. 다시 이 10개의 모든 부분집합을 만들어 빈 입력, 동률 종료, 맞닿은 구간, 서로 겹치는 구간을 포함한 1,024개 입력을 검사한다.

검증 조건과 실패 정보. 개수만 같다고 충분하지 않다. 겹치는 요청을 잘못 반환했는데 우연히 개수가 같을 수도 있다. 따라서 선택 결과의 가능성과 최적 개수를 함께 검사한다. 실패하면 입력, 선택 결과, 느린 정답을 담은 예외를 발생시킨다. 일반 if로 검사하므로 실행 옵션에 따라 검사가 생략되지 않는다.

main의 실행 순서. 먼저 예시를 풀고 선택 목록과 개수를 출력한다. 그다음 전수 대조가 정상 종료한 경우에만 통과 수를 출력한다. 검증 전체에는 지수적으로 늘어나는 조사가 들어 있으므로 검증용 시각 범위를 실제 요청 규모로 확대해서는 안 된다. 실제 풀이 함수의 복잡도와 검증 프로그램의 비용을 구분해야 한다.

이 대조는 정한 작은 세계 안에서 모든 입력을 확인한다는 뜻이다. 더 큰 시각, 같은 구간을 가진 별도 요청, 다른 입력 조건까지 모두 검사했다는 뜻은 아니다. 일반적인 정당성은 교환 논증이 담당하고, 전수 대조는 구현이 그 논증을 제대로 옮겼는지 확인하는 역할을 한다.

실행 결과

macOS나 Linux에서 main.py가 있는 디렉터리로 이동한 뒤 다음 명령을 실행한다. Python 3.12 이상의 표준 라이브러리만 사용하며 외부 패키지를 설치할 필요가 없다. 첫 명령은 문법 컴파일을 확인하고, 두 번째 명령은 프로그램을 실행한다.

python3 -W error -m py_compile main.py
python3 main.py

컴파일 명령은 성공하면 출력이 없다. 프로그램의 예상 출력은 다음과 같다.

선택: 나, 다, 라
최대 개수: 3
작은 입력 전수 대조: 1024개 통과

마지막 줄은 검증 입력 1,024개에 대해 선택 결과가 겹치지 않고, 그 개수가 느린 정답과 같았음을 뜻한다. 서로 다른 최적 목록이 있을 수 있으므로 목록 자체의 일치 여부는 비교하지 않는다.

실무에서 자주 틀리는 것

종료 시각 대신 시작 시각으로 정렬한다

데이터를 시간순으로 처리한다는 말만 기억하면 시작 시각을 기준으로 정렬하기 쉽다. 하지만 이 문제에서 보존하려는 것은 다음 요청을 받을 여유이며, 교환 논증도 종료 시각을 비교한다. 다음은 틀린 정렬 기준이다.

ordered = sorted(requests, key=lambda request: request[1])

종료를 첫 기준으로 고친다. 동률 기준은 결과가 일정하도록 명시한다.

ordered = sorted(
    requests,
    key=lambda request: (request[2], request[1], request[0]),
)

경계에서 맞닿은 요청을 제외한다

종료 시각을 포함하지 않는다는 조건을 놓치면 시작과 마지막 종료가 같은 요청을 제외하게 된다. 다음 코드는 [1, 2) 뒤의 [2, 3)을 승인하지 못한다.

if last_end is None or start > last_end:
    chosen.append(request)
    last_end = end

이 장의 조건에서는 등호를 포함해야 한다. 정리 시간이 필요하다면 그 시간을 반영한 새 조건을 먼저 정의해야 한다.

if last_end is None or start >= last_end:
    chosen.append(request)
    last_end = end

제외한 요청의 종료까지 경계에 반영한다

다음 코드는 승인하지 않은 요청도 last_end를 바꾼다. 첫 예에서 가를 제외한 뒤 경계가 4가 되어, 3에 시작하는 라까지 잘못 제외할 수 있다.

if last_end is None or start >= last_end:
    chosen.append(request)
last_end = end

경계는 마지막으로 확인한 요청이 아니라 마지막으로 승인한 요청을 나타내야 한다. 갱신을 조건문 안에 둔다.

if last_end is None or start >= last_end:
    chosen.append(request)
    last_end = end

요청이 아니라 시각 쌍만 남긴다

동일한 시각의 요청 두 개도 서로 다른 예약일 수 있다. 이름을 버리고 집합으로 바꾸면 입력의 요청 수와 선택 결과의 의미가 달라진다. 양의 길이인 동일 구간 두 개를 동시에 승인할 수는 없지만, 어느 요청을 승인했는지는 남겨야 한다.

requests = list({(start, end) for name, start, end in requests})

요청을 식별하는 이름과 시각을 함께 보존한다. 완성 코드의 함수들도 이 세 항목 구조를 기준으로 동작한다.

requests = [
    (name, start, end)
    for name, start, end in requests
]

한눈에 보기

일정 선택 그리디의 적용 조건과 확인할 근거

항목	핵심 내용	확인 방법
목표	겹치지 않는 요청의 최대 개수	점수 합계와 구분한다
입력 조건	공간 하나, 양의 길이, 분할 불가	시작이 종료보다 작은지 본다
선택 기준	가능한 요청 중 가장 빠른 종료	정렬 기준의 첫 항목을 본다
가능 조건	시작이 마지막 종료 이상	맞닿은 두 구간으로 시험한다
정당성	최적 목록의 첫 요청을 교환해도 개수 유지	뒤의 요청이 계속 가능한지 본다
빠른 풀이 비용	시간 O(n log n), 추가 공간 O(n)	정렬과 결과 목록을 포함한다
구현 검증	작은 입력에서 모든 선택을 조사	가능성과 최적 개수를 함께 비교한다

그리디를 설계할 때는 먼저 선택 기준을 한 문장으로 적는다. 그다음 어떤 최적해의 어느 부분을 바꿀 것인지 정한다. 교환 뒤 조건이나 목적값을 보존할 수 없다면, 그 지점을 이용해 작은 반례를 만들어 본다. 구현을 시작하기 전에 선택 기준의 근거를 분명히 하면 코드의 비교 연산과 갱신 위치도 자연스럽게 정해진다.

연습 문제

1. 첫 번째 작업실 문제의 다섯 요청을 종료 시각이 큰 순서로 골라 본다고 하자. 첫 선택이 마라면 이후 그 앞에 붙일 수 있는 요청을 어떻게 고를 수 있는가. 가장 늦게 시작하는 요청부터 역방향으로 고르는 규칙을 한 문장으로 정하고, 첫 선택을 교환하는 근거를 설명하라.
2. 완성 코드의 승인 조건을 start > last_end로 바꾸었을 때 실패하는 두 요청을 직접 만들라. 올바른 정답과 수정된 코드의 결과를 각각 적어라.
3. 모든 요청 뒤에 정리 시간 1이 필요하다. 단, 마지막 요청 뒤의 정리는 다른 요청의 승인 여부에 영향을 주지 않는다. 승인 조건을 어떻게 바꾸어야 하는가. 정리 시간이 모든 요청에서 같을 때 기존 종료 시각 정렬을 유지할 수 있는 이유도 설명하라.
4. 전수 대조의 구간 생성 범위를 0부터 5까지로 늘린다고 하자. 만들 수 있는 구간 수와 입력 부분집합 수를 구하라. 이때 빠른 풀이보다 검증이 급격히 무거워지는 이유를 설명하라.

정답과 해설

1. 역방향 규칙은 “이미 고른 첫 일정 앞에 놓을 수 있는 요청 중 시작이 가장 늦은 것을 고른다”이다. 처음에는 모든 요청 중 시작이 가장 늦은 마를 고르고, 종료가 4 이하인 요청 중 시작이 가장 늦은 다를 고른 뒤 나를 고른다. 실제 진행 순서로는 나, 다, 마의 3개다. 어떤 최적 목록의 마지막 요청을 시작이 가장 늦은 요청으로 바꾸면, 앞의 요청은 원래 마지막 요청의 시작 이하에서 끝난다. 바꾼 요청은 그보다 같거나 늦게 시작하므로 앞의 요청을 유지할 수 있다. 정방향 규칙과 마찬가지로 남은 부분에서 같은 교환을 반복한다.
2. 예를 들어 가 [0, 1), 나 [1, 2)를 만들 수 있다. 올바른 조건은 두 요청을 모두 승인하여 2를 반환한다. 등호를 뺀 조건은 가를 승인한 뒤 나의 시작 1이 마지막 종료 1보다 크지 않다고 판단하여 1을 반환한다. 구간이 맞닿는 입력은 경계 조건을 확인하는 작은 시험이다.
3. 첫 선택이 아니라면 start >= last_end + 1로 검사한다. 완성 코드의 조건은 last_end is None or start >= last_end + 1이 된다. 선택 뒤 last_end에는 원래 종료 시각을 저장한다. 모든 요청의 종료에 같은 1을 더해도 종료 순서는 바뀌지 않는다. 따라서 가장 빨리 작업실을 다시 사용할 수 있게 하는 요청이 원래 종료도 가장 빠른 요청이며, 같은 교환 논증이 성립한다. 마지막 정리 시간에 별도의 마감 제한이 없다는 조건도 필요하다.
4. 구간 수는 5 + 4 + 3 + 2 + 1 = 15개이고, 입력 부분집합은 2의 15제곱인 32,768개다. 각 입력 안에서도 선택 부분집합을 다시 조사하므로 입력 개수 증가만 생각해서는 부족하다. 입력과 그 안의 선택을 함께 세면 구간마다 입력에서 빠짐, 입력에 있지만 선택하지 않음, 입력에 있고 선택함의 세 상태가 있다. 따라서 쌍 검사 전의 선택 후보 조사 횟수도 구간 수 m에 대해 3의 m제곱으로 증가한다. 전수 대조는 작은 범위에 두고 실제 크기의 요청은 그리디 함수로 처리해야 한다.