불변조건·종료와 반례 찾기

유클리드 알고리즘의 이유를 설명하고 탐욕 선택의 한계를 반례로 확인합니다.

예 몇 개가 맞는 것과 방법이 항상 맞는 것은 다릅니다. 목표는 반복 중 유지되는 사실을 찾고, 종료를 보이는 값과 잘못된 주장을 깨는 반례를 구분하는 것입니다. 나머지 연산·반복·문제 명세를 복습하세요.

개념과 약속

불변조건은 반복 전과 매 단계 뒤에 유지되는 사실입니다. 최대공약수 gcd(a,b)는 두 정수를 나누어떨어지게 하는 가장 큰 양의 정수입니다. 아래 구현은 부호를 없애고 gcd(0,0)은 0으로 약속합니다. a = q*b + r이면 a와 b를 모두 나누는 수는 b와 r도 나누고, 그 역도 성립합니다. 따라서 gcd(a,b) = gcd(b,a%b)입니다.

종료를 보이려면 상태가 바뀐다는 말보다 음수가 아닌 값이 엄격히 줄어든다는 설명이 필요합니다. 반면 탐욕법은 지금 보이는 가장 좋은 선택을 합니다. 큰 동전부터 쓰는 방법은 어떤 동전 집합에서는 좋지만 임의의 동전에서 최소 개수를 보장하지 않습니다. 확률을 사용하는 알고리즘도 정확성 검토가 필요합니다. 결과가 항상 맞고 실행 시간이 확률적인 경우와 오답 확률을 허용하는 경우는 다른 약속입니다.

손으로 상태 추적하기

a	b	a % b	다음 상태
48	18	12	`(18, 12)`
18	12	6	`(12, 6)`
12	6	0	`(6, 0)`

금액 6, 동전 [4,3,1]의 탐욕 선택은 4+1+1로 세 개입니다. 3+3 두 개라는 더 좋은 답 하나가 '언제나 최적'이라는 주장을 깨뜨립니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

abs는 절댓값, %는 나머지입니다. 동전 코드의 set(coins)는 중복 단위를 없애고 sorted(..., reverse=True)는 큰 단위부터 놓습니다. //는 정수 나눗셈의 몫이며 raise ValueError는 입력 약속 위반을 알립니다.

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


def greedy_change(amount, coins):
    if amount < 0 or any(coin <= 0 for coin in coins):
        raise ValueError("nonnegative amount and positive coins required")
    result = []
    for coin in sorted(set(coins), reverse=True):
        count, amount = divmod(amount, coin)
        result.extend([coin] * count)
    if amount:
        raise ValueError("these coins cannot express the amount greedily")
    return result


print(gcd(48, 18))
print(gcd(-48, 18))
print(gcd(0, 0))
print(greedy_change(6, [4, 3, 1]))