5 / 16강

지금 좋은 선택을 하는 탐욕법

탐욕법은 현재 가장 좋아 보이는 선택을 확정하고 다음 단계로 넘어갑니다. 되돌아가는 일을 줄여 풀이가 간단해질 수 있지만, 그 선택이 최종 정답으로 이어지는 이유가 필요합니다.

큰 동전부터 고르면 될까요?

동전이 1, 3, 4원이고 6원을 만들어야 한다고 합시다. 큰 동전부터 고르면 4 + 1 + 1로 3개입니다. 하지만 3 + 3이면 2개입니다. ‘지금 가장 큰 동전’이라는 선택이 전체 동전 수를 최소화하지 못합니다.

이런 예를 반례라고 합니다. 모든 입력에 맞는다는 주장은 반례 하나로 틀렸음을 보일 수 있습니다.

종료 시간이 빠른 회의부터 고르기

한 회의실에서 겹치지 않는 회의를 최대한 많이 열려 합니다. 각 회의의 가치는 같고, 끝나는 시각과 다음 시작 시각이 같으면 이어서 열 수 있다고 하겠습니다.

meetings = [(0, 2), (1, 5), (2, 4), (4, 6)]
chosen = []
last_end = float("-inf")
for start, end in sorted(meetings, key=lambda item: item[1]):
    if start >= last_end:
        chosen.append((start, end))
        last_end = end
print(chosen)

선택 결과는 [(0, 2), (2, 4), (4, 6)]입니다. 가장 먼저 끝나는 회의를 고르면 뒤에 남는 시간이 가장 넓습니다.

최적의 일정이 다른 첫 회의를 골랐더라도, 그 회의를 가장 먼저 끝나는 회의로 바꿔도 뒤의 회의가 밀리지 않습니다. 첫 선택을 이렇게 바꿀 수 있다는 교환 논증으로 탐욕 선택의 근거를 세웁니다. 남은 회의에도 같은 논리를 적용합니다.

정렬에 O(n log n), 한 번 훑는 데 O(n)이 걸립니다. 전체 시간은 O(n log n)입니다.

조건이 바뀌면 다시 생각합니다

회의마다 수익이 다르면 ‘많이 열기’와 ‘수익 합 최대화’는 다른 문제입니다. 종료 시간이 빠른 순서가 최대 수익을 보장하지 않습니다. 탐욕법이 항상 틀린 것도, 항상 맞는 것도 아닙니다. 선택 규칙과 문제 조건을 함께 증명해야 합니다.

확인 문제

회의 A는 03시, B는 01시, C는 12시, D는 23시입니다. 처음에 A를 고르면 최대로 많은 회의를 열 수 있을까요?