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

예를 몇 개 넣어 봤더니 답이 맞았다고 해서 방법이 언제나 맞는 것은 아닙니다. 그렇다고 모든 입력을 넣어 볼 수도 없습니다. 이 글에서는 알고리즘이 맞는다고 말할 수 있는 근거 두 가지를 익힙니다. 하나는 반복할 때마다 유지되는 성질이고, 다른 하나는 반복이 반드시 끝난다는 설명입니다. 그리고 그럴듯해 보이는 주장을 단 하나의 예로 무너뜨리는 반례도 함께 다룹니다. 앞 글의 명세와 1장의 불변조건을 떠올리며 읽으면 됩니다.

최대공약수를 구하는 오래된 방법

두 정수의 최대공약수(greatest common divisor, gcd)는 두 수를 모두 나누어떨어지게 하는 가장 큰 양의 정수입니다. 48과 18의 공약수는 1, 2, 3, 6이므로 최대공약수는 6입니다. 약수를 모두 나열해 비교할 수도 있지만, 수가 커지면 그 방법은 금방 느려집니다. 대신 2,000년도 더 전에 기록된 유클리드 알고리즘(Euclidean algorithm)을 씁니다.

방법은 간단합니다. 두 수 a와 b에서 b가 0이 아니면 a를 b로 나눈 나머지를 구하고, 상태를 (b, 나머지)로 바꿉니다. 이것을 b가 0이 될 때까지 되풀이하면, 그때의 a가 최대공약수입니다. 48과 18로 따라가 보겠습니다.

b가 0이 됐을 때 a는 6이고, 실제로 48과 18의 최대공약수도 6입니다. Python으로 옮기면서 각 단계의 상태도 출력해 봅니다. abs는 절댓값을 구하는 함수로, 음수가 들어와도 같은 방식으로 계산하려고 먼저 부호를 없앱니다.

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


print(gcd_trace(48, 18))

48 18 12
18 12 6
12 6 0
6

while b:는 while b != 0:과 같은 뜻입니다. Python에서 정수 0은 조건 자리에서 거짓으로, 0이 아닌 정수는 참으로 취급되기 때문입니다. 출력의 세 줄은 표의 세 줄과 정확히 같습니다.

바뀌는 상태 속에서 변하지 않는 것

이 방법이 왜 맞을까요? 상태는 (48, 18)에서 (18, 12), (12, 6), (6, 0)으로 계속 바뀌지만, 바뀌지 않는 것이 하나 있습니다. 바로 두 수의 최대공약수입니다. 네 상태 모두 최대공약수가 6입니다. 이처럼 반복 전에도 참이고 한 단계를 거친 뒤에도 여전히 참인 성질을 불변조건(invariant)이라고 합니다. 1장에서 반복마다 참으로 남는다고 본 성질이 바로 이것입니다.

최대공약수가 보존되는 이유는 나눗셈의 성질에서 나옵니다. a를 b로 나눈 몫을 q, 나머지를 r이라 하면 a = q × b + r입니다. 어떤 수 d가 a와 b를 모두 나눈다면, d는 a에서 q × b를 뺀 r도 나눕니다. 반대로 d가 b와 r을 모두 나눈다면, d는 q × b에 r을 더한 a도 나눕니다. 따라서 (a, b)의 공약수와 (b, r)의 공약수는 정확히 같은 집합이고, 그 가운데 가장 큰 값인 최대공약수도 같습니다.

불변조건만으로는 아직 답이 무엇인지 알 수 없습니다. 반복이 끝나는 순간의 상태와 연결해야 합니다. 반복은 b가 0일 때 멈추는데, 어떤 수 a와 0의 최대공약수는 a 자신입니다. 0은 모든 수로 나누어떨어지므로, a와 0을 함께 나누는 가장 큰 수는 a이기 때문입니다. 처음 입력의 최대공약수가 끝까지 보존됐고, 끝난 상태의 최대공약수가 a이므로, 함수가 돌려주는 a가 바로 처음 입력의 최대공약수입니다.

두 수가 모두 0이면 공약수가 무한히 많아서 "가장 큰 공약수"가 정의되지 않습니다. 이 구현은 그 경우 반복을 한 번도 하지 않고 0을 돌려주는데, 이는 Python 표준 라이브러리의 math.gcd(0, 0)이 0을 돌려주는 것과 같은 약속입니다. 이처럼 수학적으로 정의되지 않는 입력은 명세에서 따로 정해 두어야 합니다.

반복이 끝난다는 것을 보이는 방법

맞는 답에 도착한다는 설명은 반복이 끝난다는 전제가 있어야 의미가 있습니다. 끝나지 않는 반복은 아무 답도 내지 않기 때문입니다. 종료를 보일 때 "상태가 계속 바뀌니까 언젠가 끝난다"는 말로는 부족합니다. 상태가 바뀌어도 같은 곳을 영원히 돌 수 있기 때문입니다.

필요한 것은 음수가 될 수 없으면서 매 단계 반드시 줄어드는 값입니다. 유클리드 알고리즘에서는 b가 그 역할을 합니다. b가 양수일 때 나머지 a % b는 0 이상 b 미만이므로, 다음 단계의 b는 지금의 b보다 엄격히 작습니다. 0 이상의 정수가 계속 줄어들 수는 없으므로, 유한한 단계 안에 b는 0이 되고 반복은 끝납니다. 종료를 보이는 데 쓰는 이런 값을 영어로는 variant라고 부릅니다. 1장의 카운트다운에서 remaining이 1씩 줄어 0에 닿았던 것도 같은 논리입니다.

더 깊이: 유클리드 알고리즘이 빠른 이유

b가 1씩 줄어든다면 단계 수는 b만큼 많아질 수 있습니다. 하지만 실제로는 훨씬 빨리 줄어듭니다. a ≥ b일 때 나머지 a % b는 항상 a의 절반보다 작습니다. b가 a의 절반 이하라면 나머지는 b보다 작으니 당연히 절반보다 작고, b가 a의 절반보다 크다면 나머지는 a - b가 되어 역시 절반보다 작기 때문입니다. 두 단계가 지나면 큰 쪽의 수가 이 나머지가 되므로, 두 단계마다 큰 쪽이 적어도 절반으로 줄어듭니다. 그래서 단계 수는 수의 크기가 아니라 자릿수에 비례해 늘어납니다.

가장 오래 걸리는 입력은 89와 55처럼 이웃한 피보나치 수입니다. 이 경우 마지막 단계(2를 1로 나누기)를 빼면 몫이 매번 1이라 수가 가장 느리게 줄어드는데, 그래도 9단계면 끝납니다. 이 성질을 증명한 사람의 이름을 따서 라메의 정리(Lamé's theorem)라고 합니다.

큰 동전부터 고르면 최소일까

이번에는 그럴듯하지만 틀린 주장을 보겠습니다. 거스름돈을 가장 적은 개수의 동전으로 주려면 "가장 큰 동전부터 쓸 수 있는 만큼 쓰면 된다"는 생각입니다. 이렇게 매 순간 지금 보기에 가장 좋은 선택을 하는 방법을 탐욕법(greedy method)이라고 합니다. 우리가 쓰는 500원, 100원, 50원, 10원 동전에서는 이 방법이 실제로 최소 개수를 줍니다. 하지만 동전 단위가 바뀌어도 언제나 그럴까요?

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(greedy_change(6, [4, 3, 1]))

[4, 1, 1]

코드부터 읽어 봅니다. set(coins)는 겹치는 단위를 없애고, sorted(..., reverse=True)는 큰 단위부터 늘어놓습니다. divmod(amount, coin)은 몫과 나머지를 한 번에 구하는데, 몫은 그 동전을 쓸 개수이고 나머지는 남은 금액입니다. [coin] * count는 같은 동전을 count개 담은 리스트이고, extend로 결과에 이어 붙입니다. 맨 앞의 검사는 금액이 음수이거나 0 이하인 동전이 들어오면 명세를 어긴 입력이라고 알리는 부분입니다. or는 양쪽 조건 가운데 하나라도 참이면 참이 되고, any(coin <= 0 for coin in coins)는 리스트 컴프리헨션과 같은 모양으로 동전마다 coin <= 0을 계산해 그중 하나라도 참이면 True를 돌려줍니다. raise ValueError(...)는 그 자리에서 오류를 일으켜 함수를 멈춥니다.

결과를 보면 금액 6을 동전 [4, 3, 1]로 만들 때 4 하나와 1 두 개, 모두 세 개를 씁니다. 그런데 3 두 개를 쓰면 동전 두 개로 충분합니다. 이 예 하나로 "큰 동전부터 고르면 언제나 최소 개수"라는 주장은 거짓이 됩니다. 이처럼 주장을 깨뜨리는 예를 반례(counterexample)라고 합니다.

탐욕법은 더 나쁘게 틀릴 수도 있습니다. 1원짜리 동전이 없는 [4, 3]으로 6을 만들어 보면, 4를 먼저 쓰고 남은 2를 3으로 만들 수 없어서 함수는 ValueError를 일으킵니다. 3 두 개라는 답이 분명히 있는데도 찾지 못한 것입니다. 첫 선택인 4가 이후의 선택지를 막아 버렸기 때문입니다. 금액과 동전 단위가 무엇이든 최소 개수를 구하는 방법은 9장의 동적 계획법에서 다룹니다.

반례와 증명의 관계

"모든 입력에서 맞다"는 주장은 반례가 하나만 있어도 거짓입니다. 반면 반례를 찾지 못했다는 것은 주장이 참이라는 증명이 되지 못합니다. 아직 그 입력을 시도하지 않았을 수도 있기 때문입니다. 그래서 알고리즘이 맞는다는 근거는 여러 겹으로 쌓습니다. 작은 입력으로 결과를 확인하는 검사는 실수를 빨리 찾아 주고, 불변조건은 모든 입력에서 답이 맞는 이유를 설명하며, 줄어드는 값은 반복이 반드시 끝난다는 것을 보여 줍니다. 셋은 서로를 대신하지 않고 보완합니다.

반례를 찾을 때는 무작정 많은 입력을 넣기보다 주장이 기대는 가정을 찾아 흔들어 보는 편이 빠릅니다. 탐욕법은 "큰 동전을 쓰면 남은 문제가 쉬워진다"는 가정에 기대고 있었고, 큰 동전이 작은 동전 여러 개의 조합을 방해하도록 단위를 고르자 바로 반례가 나왔습니다.

더 깊이: 무작위를 쓰는 알고리즘의 약속

뒤에서는 무작위 선택을 쓰는 알고리즘도 만납니다. 이런 알고리즘은 "맞는다"는 말의 뜻부터 정해야 합니다. 결과는 언제나 맞고 실행 시간만 운에 따라 달라지는 경우가 있고, 정해진 시간 안에 끝나지만 아주 낮은 확률로 틀린 답을 낼 수 있는 경우가 있습니다. 앞의 것을 라스베이거스 알고리즘(Las Vegas algorithm), 뒤의 것을 몬테카를로 알고리즘(Monte Carlo algorithm)이라고 부릅니다. 두 약속은 서로 다르므로, 무작위 알고리즘을 쓸 때는 어느 쪽인지 명세에 적어야 합니다.

정리

• 불변조건은 반복 전에도 참이고 한 단계를 거친 뒤에도 참인 성질입니다. 반복이 끝난 상태와 연결하면 답이 맞는 이유가 됩니다.
• 유클리드 알고리즘에서는 (a, b)와 (b, a % b)의 최대공약수가 같다는 것이 불변조건이고, b가 0일 때의 a가 답입니다.
• 종료를 보이려면 음수가 될 수 없으면서 매 단계 엄격히 줄어드는 값을 찾습니다. 유클리드 알고리즘에서는 b가 그 값입니다.
• 큰 동전부터 고르는 탐욕법은 동전 [4, 3, 1]에서 금액 6에 세 개를 쓰지만, 3 두 개가 더 적습니다. 반례 하나로 "언제나 최소"라는 주장은 무너집니다.
• 반례가 없다는 것은 증명이 아닙니다. 검사, 불변조건, 종료 설명을 함께 써서 근거를 쌓습니다.

연습 문제

1. 35와 10의 최대공약수

gcd(35, 10)을 유클리드 알고리즘으로 구할 때 상태가 어떻게 바뀌는지 끝까지 적어 보세요.

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


print(gcd_trace(35, 10))

35 10 5
10 5 0
5

2. 동전 [5, 4, 1]로 8 만들기

금액 8을 동전 [5, 4, 1]로 만들 때 탐욕법의 결과와 최소 개수의 결과를 비교해 보세요.

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(greedy_change(8, [5, 4, 1]))

[5, 1, 1, 1]

3. 종료를 보이는 값 찾기

다음 함수는 양의 정수 n을 받아 n이 1이 될 때까지 짝수면 2로 나누고 홀수면 1을 뺍니다. 이 반복이 반드시 끝나는 이유를 줄어드는 값으로 설명해 보세요.

def steps_to_one(n):
    steps = 0
    while n > 1:
        if n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps


print(steps_to_one(10))

4

다음 글 입력 크기·O·Ω·Θ와 정보의 개수에서는 맞는 방법들 사이에서 어느 쪽이 더 적은 비용으로 끝나는지 비교하는 언어를 익힙니다.