문제에서 알고리즘으로

요약

이 수업에는 코드가 없는데, 실수로 빠뜨린 것이 아니다. 알고리즘은 프로그램보다 앞서며, 무엇을 해야 하는지 정확히 기술하지 못하는 사람은 그것을 C++로도 말하지 못한다. 먼저 문제를 명세하는 법, 즉 어떤 자료를 받고, 어떤 결과를 내야 하며, 둘을 어떤 관계가 잇는지 선언하는 법을 배우고, 같은 문제 진술이 서로 다른 명세를 허용한다는 것을 보인다. 이어서 알고리즘을 유한하고 명확하며 일반적인 절차로 정의하고, 거듭된 뺄셈에 의한 나눗셈 알고리즘을 번호 매긴 단계로 쓴다. 추적표로 알고리즘을 손으로 따라가는 법을 배우는데, 추적표는 강좌 내내 이해하고 디버깅하기 위한 첫째 도구가 된다. 단계를 결합하는 세 가지 방식(순차, 선택, 반복)을 소개하는데, 모든 알고리즘은 이것들로 쓰인다. 그리고 매 회차마다 줄어들며 끝없이 내려갈 수는 없는 양을 이용해, 반복이 종료한다는 것을 정당화하는 법을 배운다.

학습 목표

간단한 문제를 입력, 출력, 그리고 그것들이 만족해야 할 조건을 밝혀 명세한다.
알고리즘을 모호함 없이, 선택과 반복을 명시하여, 번호 매긴 단계로 기술한다.
추적표로 알고리즘을 손으로 따라가고 주어진 입력에 대한 결과를 구한다.
주어진 절차에서 순차, 선택, 반복을 구별하고, 반복이 종료한다는 것을 정당화한다.

계산 문제란 무엇인가

계산 문제는 두 종류의 자료 사이의 관계이다. 하나는 받는 자료로 입력이라 하고, 다른 하나는 내야 하는 자료로 출력이라 한다. 이를 푼다는 것은 한 경우에 대한 답을 얻는 것이 아니라, 허용되는 모든 입력에 대해 그 관계를 만족하는 출력을 만들어 내는 방법을 갖는 것이다. “17을 5로 나누면 얼마인가?”는 질문이고, “두 정수가 주어질 때 그 몫과 나머지를 구하라”는 문제이다. 모든 정수 쌍에 대해 한꺼번에 말하기 때문이다.

그런데 일상 언어는 부정확해서, 같은 문제 진술도 여러 가지로 이해될 수 있다. 그래서 풀기 전에 명세한다. 무엇이 들어오고, 무엇이 나가며, 각각이 어떤 조건을 만족해야 하는지 적는 것이다. 명세는 세 부분으로 이루어진다. 입력은 자료를 그 종류(정수, 소수점이 있는 수, 단어)와 함께 열거하고, 그것들에 요구되는 조건을 열거하는데, 이 조건을 사전 조건이라 한다. 해법을 사용하는 사람은 이를 지키기로 약속한다. 출력은 결과들을 열거한다. 관계, 곧 사후 조건은 출력이 입력에 대해 무엇을 만족해야 하는지 말한다. 해법을 쓰는 사람은 사전 조건이 지켜지기만 하면 이를 보장하기로 약속한다. 이로부터 명세는 문제를 내는 사람과 푸는 사람 사이의 계약이며, 사전 조건 밖에서는 해법이 아무것도 약속하지 않는다는 결론이 나온다.

예시세 수의 최댓값

일상적인 문제 진술: “세 수 가운데 가장 큰 것을 찾아라”. 명세:

입력: 세 수 $x$ , $y$ , $z$ (정수 또는 소수점이 있는 수, 다른 조건 없음).
출력: 수 $m$ 하나.
관계: $m$ 은 세 자료 가운데 하나이고, 그 가운데 어느 것도 $m$ 보다 크지 않다. 즉 $m \geq x$ , $m \geq y$ , 그리고 $m \geq z$ 이다.

관계는 “셋 가운데 가장 큰 것”이라고 말하지 않는다. 그것이야말로 명확히 하고 싶었던 것이기 때문이다. 대신 확인할 수 있는 두 조건을 준다. 첫째 조건은 $m$ 이 자료 가운데 하나일 것을 요구하고(이 조건이 없으면 수 1000이 거의 어떤 입력에 대해서도 둘째 조건을 만족한다), 둘째 조건은 어느 자료도 그것을 넘지 않을 것을 요구한다. 그리고 명세는 문제 진술이 열어 둔 의문을 덤으로 해결한다. 두 자료가 최댓값에서 같을 때, 예컨대 $(4, 9, 9)$ 에서 출력은 $9$ 이며, 거기에는 아무 오류도 없다.

같은 문제 진술은 서로 다른 명세를 허용하며, 그 가운데 하나를 고르는 것은 결정이지 부주의가 아니다. 가장 교훈적인 경우는 정수 나눗셈이다. 정수 $a \geq 0$ 과 $b > 0$ 에 대해서는 모두가 동의한다. 몫 $q$ 와 나머지 $r$ 은 다음을 만족하는 유일한 정수이다.

a = b \cdot q + r, \quad 0 \leq r < b

이리하여 $a = 17$ , $b = 5$ 일 때 $q = 3$ , $r = 2$ 이다. $17 = 5 \cdot 3 + 2$ 이기 때문이다. 그러나 “두 정수를 나누어라”라는 문제 진술은 $a$ 가 음수일 때 어떻게 할지 말하지 않으며, 이 물음은 쓸데없는 것이 아니다. $a = -7$ , $b = 2$ 일 때 합리적인 답이 두 가지 있다.

예시피제수가 음수인 나눗셈의 두 명세

첫째 명세: 나머지는 결코 음수가 아니다, $0 \leq r < b$ . 그러면 $-7 = 2 \cdot (-4) + 1$ 이고, 출력은 $q = -4$ , $r = 1$ 이다. 이것이 수학에서 공부하는 것으로, 강좌 「대수학과 기하학 I」의 수업 「나누어떨어짐과 나머지가 있는 나눗셈」에서 다룬다.

둘째 명세: 몫은 소수점까지 나눈 결과에서 소수 부분을 버린 것, 즉 0 쪽으로 반올림한 것이고, 나머지는 모자라는 부분으로 피제수와 같은 부호를 갖는다. 그러면 $-7 / 2 = -3.5$ 의 소수 부분을 버려 $-3$ 이 되고, $-7 = 2 \cdot (-3) + (-1)$ 이다. 출력은 $q = -3$ , $r = -1$ 이다.

둘 다 $a = b \cdot q + r$ 을 만족하며, 나머지에 부과하는 조건이 다르다. 어느 쪽도 오류는 아니지만, 한쪽을 쓰면서 다른 쪽을 쓰고 있다고 믿는 프로그램은 음수에서 틀린 결과를 낸다. 미리 하나 알려 두자. C++는 둘째 것을 택하며, 이는 산술 연산 수업에서 보게 된다. 첫째 것을 기대하는 사람은 놀라게 될 것이다.

셋째 선택지도 있는데, 실제로는 이것이 가장 흔하다. 사전 조건으로 그 경우를 제외하는 것이다. 명세가 $a \geq 0$ 을 요구하면 음수 문제는 사라진다. 해결되었기 때문이 아니라, 해법을 쓰는 사람이 그것을 제기하지 않기로 약속했기 때문이다. 해서는 안 되는 것은 문제를 결정하지 않은 채 남겨 두는 것이다. 같은 이유로 명세는 $b > 0$ 을 요구한다. $b = 0$ 일 때에는 관계를 만족하는 $q$ 와 $r$ 이 존재하지 않으며, 계약은 그것을 밝혀야 한다.

흔한 오류는 예로 명세하는 것이다. “17과 5에 대한 출력은 3과 2이다”. 예는 설명은 하지만 명세는 하지 못한다. 다른 입력에서 무슨 일이 일어나는지 말하지 않기 때문이다. 서로 다른 무수히 많은 관계가 한 경우에서는 일치한다. 명세는 일반적인 조건으로 쓰고, 예는 나중에 그것을 확인하는 데 쓴다.

알고리즘

문제를 명세하고 나면 그것을 풀 방법을 찾는다. 알고리즘이란, 사전 조건을 만족하는 어떤 입력에 적용하더라도 유한한 수의 단계 안에 사후 조건을 만족하는 출력을 만들어 내는 명령의 열이다. 이 정의에는 세 가지 요건이 들어 있다.

유한성. 알고리즘은 유한한 수의 명령으로 쓰이고, 허용되는 각 입력에 대해 그 가운데 유한한 수를 실행한 뒤 종료한다. 어떤 입력에 대해 영원히 계속되는 절차는 그 입력에 대한 알고리즘이 아니다.
명확성. 각 명령은 단 하나의 의미를 가지며, 그것을 실행하는 사람은 언제나 무엇을 해야 하는지, 다음 명령이 무엇인지 안다. 어떤 결정도 실행하는 사람의 판단에 맡겨지지 않는다.
일반성. 알고리즘은 한 경우만이 아니라 허용되는 모든 입력에 대해 문제를 푼다.

조금 느슨하게는, 명확하고 종료하지만 허용되는 어떤 입력에 대해 사후 조건을 만족하지 않는 절차도 알고리즘이라고 부른다. 엄밀히 말하면 그것은 다른 문제에 대한 알고리즘이며, 명세된 문제에 대해서는 올바르지 않다고 말하겠다. 이 수업의 문제들에서는 이렇게 말하며, 반례로 올바르지 않은 알고리즘을 반박한다.

요리법은 알고리즘과 닮아서 흔히 비교 대상이 된다. 그러나 거의 어떤 요리법도 알고리즘이 아니다. “소금을 한 꼬집 넣는다”는 명확하지 않다. 한 꼬집은 양이 아니기 때문이다. “노릇해질 때까지 굽는다”는 두 사람이 서로 다르게 내릴 판단에 달려 있다. “여러 번 휘젓는다”는 몇 번인지 말하지 않는다. 요리사는 이런 빈틈을 경험으로 메우지만, 컴퓨터에는 경험이 전혀 없다. 이로부터 강좌 전체를 지배하는 요건이 나온다. 알고리즘은 문제를 이해하지 못하는 사람도 아무것도 짐작하지 않고 따라갈 수 있어야 한다. 어떤 단계를 실행하려면 그것이 무엇에 쓰이는지 알아야 한다면, 그 단계는 잘못 쓰인 것이다.

이 강좌의 알고리즘은 먼저 번호 매긴 단계로, 한국어로, 몇 가지 약속에 따라 쓴다. 알고리즘이 진행되는 동안 바뀌는 자료는 $q$ , $r$ 처럼 글자나 단어로 이름을 붙이고, 변수라고 부른다. “ $r$ 에 $r - b$ 를 대입한다”라고 써서, $r - b$ 를 $r$ 의 현재 값으로 계산하고 그 결과가 $r$ 의 새 값이 된다는 것을 나타낸다. 이전 값은 사라진다. 메모할 때 쓰는 약식 표기에서는 같은 명령을 왼쪽을 향한 화살표로 쓰며, 키보드로는 r <- r - b이다. 명령은 번호 순서대로 실행한다. 다만 어떤 명령이 달리 지시하는 경우는 예외이다.

예시거듭된 뺄셈에 의한 나눗셈

문제는 앞 절에서 명세한 것이다. 입력은 두 정수 $a \geq 0$ 과 $b > 0$ , 출력은 두 정수 $q$ 와 $r$ 로, $a = b \cdot q + r$ 및 $0 \leq r < b$ 을 만족한다. 착상은 나누어 주기이다. $a$ 에서 $b$ 씩 묶음을 할 수 있는 한 덜어 내고, 덜어 낸 묶음을 세며, 남는 것이 나머지이다.

$q$ 에 $0$ 을 대입하고, $r$ 에 $a$ 를 대입한다.
$r \geq b$ 인 동안 단계 3과 4를 반복하고, 더 이상 성립하지 않으면 단계 5로 간다.
$r$ 에 $r - b$ 를 대입한다.
$q$ 에 $q + 1$ 을 대입하고, 단계 2로 돌아간다.
$q$ 와 $r$ 을 출력하고 종료한다.

단계 2는 매번 던지는 물음이다. 첫 회차 전에, 그리고 각 회차 뒤에 묻는다. 단계 3과 4는 반복의 본문, 즉 반복되는 부분을 이룬다. 실행하는 사람의 판단에 맡겨지는 것은 아무것도 없다. 어느 때든 다음 명령은 하나뿐이다.

이 알고리즘은 느리고(백만을 셋으로 나누는 데 삼십만 회차가 넘게 걸린다), 학교에서 배우는 나눗셈 방법이 훨씬 빠르다. 그러나 올바르며, 단순하기 때문에 알고리즘에 대해 추론하는 법을 배우기에 이상적이다. 올바른 알고리즘과 효율적인 알고리즘의 차이는 알고리즘의 비용 수업에서 다시 다룬다.

끝으로, 알고리즘을 그 표기와 구별해 두는 것이 좋다. 뺄셈에 의한 나눗셈 알고리즘은 한국어로 쓰든, 그림으로 그리든, C++나 다른 어떤 프로그래밍 언어로 쓰든 같은 알고리즘이다. 그것을 정하는 것은 연산의 순서이지 말이 아니다. 프로그램은 기계가 실행할 수 있는 언어로 알고리즘을 쓴 것이며, 그 실행이 어떻게 일어나는지는 프로그램, 컴파일러, C++ 수업에서 설명한다. 그렇다면 프로그램은 아주 다른 두 가지 방식으로 틀릴 수 있다. 알고리즘이 올바르지 않은 경우로, 이때는 어떤 언어도 그것을 구하지 못한다. 또는 알고리즘은 올바르지만 잘못 쓴 경우이다. 두 경우를 구별하는 것이 디버깅 작업의 절반이며, 그래서 이 강좌는 언제나 알고리즘을 먼저 쓴다.

알고리즘을 손으로 따라가기

알고리즘을 읽는 것만으로는 그것이 무엇을 하는지 알기에 부족하다. 실행해 보아야 한다. 기계가 하듯이, 단계를 건너뛰지도 결과를 짐작하지도 않으면서 손으로 따라가는 것은 프로그래머에게 가장 쓸모 있는 기량이다. 이것으로 알고리즘을 쓰기 전에 확인하고, 프로그램을 실행하기 전에 그 출력을 예측하며, 잘못 동작하는 프로그램의 오류를 찾는다.

그 도구는 추적표이다. 실행하는 단계의 번호를 적는 열 하나, 변수마다 열 하나, 필요하면 판정하는 조건을 적는 열 하나를 두고, 실행한 단계마다 행 하나를 둔다. 각 행에는 그 단계에서 바뀐 변수의 새 값을 적고 바뀌지 않은 것은 비워 두어, 어떤 변수의 현재 값이 그 열에 마지막으로 적힌 값이 되게 한다. 조건은 그 결과와 함께 적는다.

예시17을 5로 나누는 나눗셈의 추적

거듭된 뺄셈에 의한 나눗셈을 $a = 17$ , $b = 5$ 로 따라가 본다. 그림의 화살표는 방금 실행한 단계를 가리키고, 점선은 단계 4가 단계 2로 돌아간다는 것을 상기시킨다.

증명

$(q, r) = (0, 17)$
단계 1: 초깃값을 준다. 입력은 사전 조건을 만족한다. $17 \geq 0$ 이고 $5 > 0$ 이기 때문이다.
$(q, r) = (1, 12)$
첫째 회차. 단계 2에서 $17 \geq 5$ 임이 확인되므로 본문을 실행한다. 단계 3이 다섯짜리 묶음 하나를 덜어 내고, 단계 4가 그것을 센다.
$(q, r) = (2, 7)$
둘째 회차: $12 \geq 5$ 이므로 본문을 다시 실행한다.
$(q, r) = (3, 2)$
셋째 회차: $7 \geq 5$ 이므로 본문을 다시 실행한다.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
단계 2에서 조건이 성립하지 않는다. $2 < 5$ 이기 때문이다. 알고리즘은 단계 5로 가서 $q = 3$ 과 $r = 2$ 를 출력한다. 출력은 사후 조건을 만족한다.

완성된 표는 열두 행이다. 단계 1, 각각 세 행인 세 회차(단계 2, 3, 4), 성립하지 않은 판정, 그리고 출력이다.

이 표에 대해 두 가지를 짚어 둔다. 첫째, 회차의 수는 몫 $3$ 과 같고, 단계 2는 본문보다 한 번 더 많은 $4$ 번 실행되었다. 이런 모양의 반복에서는 언제나 그렇다. 마지막 판정이 성립하지 않는 판정이기 때문이다. 둘째, 추적은 알고리즘의 글이 언뜻 보아서는 말하지 않는 것을 알려 준다. $a < b$ 일 때, 예컨대 $a = 3$ , $b = 5$ 일 때, 조건은 처음부터 성립하지 않고 본문은 한 번도 실행되지 않으며 출력은 $q = 0$ , $r = 3$ 이다. 이는 올바르다. $3 = 5 \cdot 0 + 3$ 이기 때문이다. 반복이 한 번도 실행되지 않는 경우를 잊는 것은 알고리즘을 설계할 때 가장 흔한 오류 가운데 하나이며, 작은 입력으로 하는 추적이 그것을 찾아낸다.

한 경우의 추적은 알고리즘이 올바르다는 것을 증명하지 않는다. 한 경우를 확인할 뿐이다. 그러나 잘 고른 추적(흔한 경우, 경계 경우, 반복이 한 번도 실행되지 않는 경우)은 오류의 대부분을 찾아내며, 실패하는 추적은 오류가 어디 있는지 알려 준다. 경우에서 증명으로 넘어가는 법은 올바른 반복문 설계 수업에서 가르친다.

순차, 선택, 반복

가까이에서 보면 알고리즘은 아주 적은 부품으로 만들어진다. 기본 명령(변수에 값을 주기, 결과를 내기)이 있고, 그것들을 결합하는 세 가지 방식이 있다.

순차: 한 명령 다음에 다른 명령을 차례로 실행한다. 나눗셈의 단계 3과 4는 순차이다. 먼저 빼고, 그다음에 센다.
선택: 어떤 조건이 성립하는지에 따라 한 부분이나 다른 부분을(또는 한 부분이나 아무것도 아닌 것을) 실행한다. “ $y > m$ 이면 $m$ 에 $y$ 를 대입한다”는 선택이다.
반복: 어떤 조건이 성립하는 동안 한 부분을 거듭 실행한다. 나눗셈의 단계 2는 그 본문과 함께 반복이다.

각 형식은 입구와 출구를 하나씩만 가지며, 그 내부는 다시 셋 가운데 어느 것이든 될 수 있다. 반복의 본문은 선택을 담을 수 있고, 선택의 한 갈래는 반복을 담을 수 있으며, 이런 식으로 계속된다. 그렇다면 세 형식으로 어떤 복잡도의 알고리즘이든 만들 수 있다. 서로 맞물리는 몇 가지 부품으로 어떤 건물이든 지을 수 있는 것과 같다. 이것들로 모든 알고리즘을 표현할 수 있다는 것은 프로그래밍 이론의 잘 알려진 결과이다(1966년에 코라도 뵘과 주세페 야코피니가 증명했다). 여기서는 증명하지 않지만, 강좌 전체가 그것을 확인해 준다. 이 강좌에서 쓸 프로그램은 아무리 길어도 이 세 형식 말고는 아무것도 쓰지 않으며, 그것들은 C++에서 선택은 if로, 반복은 while 또는 for로 쓰고, 조건문 수업과 반복문 수업에서 다룬다.

알고리즘의 모양을 보는 데 쓸모 있는 표기법이 순서도이다. 각 명령은 직사각형, 각 조건은 출구가 둘인 마름모로 그리고(성립하면 그림에서 $1$ , 성립하지 않으면 $0$ 으로 표시한다), 화살표는 다음 단계가 무엇인지 말해 준다. 이것은 표기법이지 목적이 아니다. 작은 알고리즘을 한눈에 보는 데는 도움이 되지만 규모가 커지면 쓸 수 없고, 큰 프로그램을 그림을 그려서 쓰는 사람은 없다.

예시세 형식과 그 합성

그림은 일반적인 명령 $A$ , $B$ 와 조건 $c$ 로 세 형식을 그리고, 이어서 그것들을 합성해 거듭된 뺄셈에 의한 나눗셈의 순서도를 만든다.

증명

$A ; B$
순차: $A$ 를 실행하고 이어서 $B$ 를 실행한다. 입구도 출구도 하나뿐이다.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
선택: $c$ 가 성립하면 $A$ 를 실행하고, 그렇지 않으면 $B$ 를 실행한다. 두 갈래는 하나의 출구에서 만난다.
$c, A, c, A, \ldots, c$
반복: $c$ 를 판정하여, 성립하면 $A$ 를 실행하고 다시 $c$ 를 판정한다. 성립하지 않으면 빠져나간다. 조건은 본문보다 한 번 더 판정된다.
$a = b \cdot q + r, \quad 0 \leq r < b$
합성: 거듭된 뺄셈에 의한 나눗셈은 순차(초깃값, 반복, 출력)이고, 그 반복은 또 다른 순차(빼기, 세기)를 본문으로 갖는다.

일상 언어로 쓰인 절차에서 세 형식을 구별하는 것이 그것을 번역하는 첫걸음이다. 선택의 신호는 “만약”, “…인 경우에”, “…에 따라”이고, 반복의 신호는 “…인 동안”, “…할 때까지”, “각 …에 대해”, “…만큼”이다. 이런 말이 하나도 없는 절차는 순차이며, 크기가 변하는 입력(수의 목록, 텍스트)을 다뤄야 한다면 반복이 빠져 있는 것이다.

종료하는가?

유한성은 알고리즘의 정의의 일부이며, 그것을 잃을 수 있는 곳은 반복뿐이다. 다섯 단계로 된 순차는 다섯 단계를 실행하고, 선택은 그 갈래 가운데 하나를 실행한다. 그러나 반복은 조건이 성립하는 횟수만큼 본문을 실행하며, 조건이 언젠가 성립하지 않게 된다는 것을 미리 보장하는 것은 아무것도 없다.

반복이 종료한다는 것을 정당화하려면, 변수들로 계산되는 양 가운데 두 조건을 만족하는 것을 찾는다. 반복이 계속되는 동안 자연수(음이 아닌 정수)이고, 매 회차마다 순감소한다는 것이다. 그렇다면 반복은 종료한다. 순감소하는 자연수의 수열은 무한할 수 없다. 매 회차가 그것을 적어도 1만큼 낮추고, 자연수 $n$ 에서 0까지는 $n$ 개보다 많은 계단이 없기 때문이다. 이런 양을 변량 또는 한계 함수라 하며, 올바른 반복문 설계 수업에서 체계적으로 사용한다.

예시뺄셈에 의한 나눗셈의 변량

거듭된 뺄셈에 의한 나눗셈에서 변량은 $r$ 이다. 반복이 계속되는 동안 $r \geq b > 0$ 이므로 $r$ 은 자연수이다. 매 회차마다 $r$ 에 $r - b$ 를 대입하는데, $b > 0$ 이므로(사전 조건) 새 값은 엄격히 더 작다. 따라서 반복은 종료하며, 많아야 $a$ 개의 회차 뒤에 종료한다(실제로는 정확히 $q$ 개의 회차, 곧 몫만큼의 회차 뒤에 종료한다).

사전 조건 $b > 0$ 이 어디에 쓰였는지 보라. $b = 0$ 일 때 알고리즘을 실행하면 단계 3은 $r$ 의 값을 바꾸지 않고, 조건 $r \geq 0$ 이 언제나 성립하여 반복은 결코 종료하지 않는다. 알고리즘이 틀린 것이 아니라, 계약이 배제한 입력을 받은 것이다. 또 $b$ 의 값이 음수라면 $r$ 의 값은 매 회차마다 커질 것이다. 사전 조건은 장식이 아니다. 추론이 성립하는 데 꼭 필요한 바로 그것이다.

변량의 두 조건은 모두 필요하며, 어느 쪽에서든 틀리기 쉽다. 자연수 $n$ 의 짝수 여부를 판정하려는 다음 절차를 생각해 보자. “ $n \neq 0$ 인 동안 $n$ 에 $n - 2$ 를 대입한다. 0에 이르면 $n$ 은 짝수였다”. 양 $n$ 은 매 회차마다 줄어드는데, 그런데도 $n$ 이 홀수이면 절차는 종료하지 않는다. $n = 5$ 일 때 $3$ , $1$ , $-1$ , $-3$ 을 지나며, 조건 $n \neq 0$ 은 결코 거짓이 되지 않는다. 만족되지 않는 것은 다른 조건이다. $n$ 은 자연수가 아니게 된다. 반복의 조건이 0 아래로 내려가는 것을 막지 않기 때문이다. 고치는 방법은 $n \geq 2$ 인 동안 반복하고, 마지막에 남은 값 $0$ 이나 $1$ 에 따라 판정하는 것이다. 이제 $n$ 은 매 회차마다 자연수이다. $n \geq 2$ 일 때에만 빼기 때문이다. 그리고 줄어든다. 절차는 종료한다.

반복이 종료하는지 판정하는 것이 늘 쉬운 것은 아니다. 유명한 예가 있다. 자연수 $n \geq 1$ 에서 시작하여, $n \neq 1$ 인 동안, $n$ 이 짝수이면 2로 나누고 홀수이면 $3n + 1$ 로 바꾼다. $n = 6$ 일 때 수열은 $6, 3, 10, 5, 16, 8, 4, 2, 1$ 이며, 종료한다. 종료하지 않는 $n$ 을 찾은 사람은 아무도 없고, 엄청나게 많은 값에 대해 컴퓨터로 확인되었다. 그러나 언제나 종료한다는 것을 증명한 사람도 없다. 이것이 콜라츠 추측으로, 수학의 미해결 문제이다. 매 회차마다 줄어드는 양은 하나도 알려져 있지 않다. 프로그래머에게 주는 교훈은 소박하고도 단단하다. 종료를 정당화할 줄 모르는 알고리즘은 아직 완성되지 않은 것이다.

흔한 오류

모호한 단계. “여러 번 반복한다”, “괜찮아질 때까지”, “적당한 수를 고른다”. 모든 단계는 문제를 이해하지 않고도 실행할 수 있어야 한다. 그렇지 않으면 잘못 쓰인 것이다.
반복이 한 번도 실행되지 않는 경우를 잊는다. 조건이 맨 앞에 있는 반복은 모두 본문을 0번 실행할 수 있다. 그 경우에 알고리즘이 무엇을 출력하는지 늘 물어야 하며, 가장 작은 입력으로 하는 추적이 그 답을 준다.
예로 명세한다. “17과 5에 대해 3과 2를 낸다”는 명세가 아니다. 관계는 일반적인 조건으로 쓰고, 예는 그것을 설명한다.
알고리즘을 그 프로그램과 혼동한다. 잘못 동작하는 프로그램은 알고리즘이 틀렸을 수도 있고 그 표기가 틀렸을 수도 있다. 알고리즘을 먼저 쓰지 않은 사람은 둘 가운데 무엇을 찾아야 할지 모른다.
종료를 당연하게 여긴다. 어떤 양이 줄어드는 것만으로는 부족하다. 반복하는 동안 자연수이기도 해야 한다.

예제

예제 1세 수 가운데 가장 큰 수, 같은 값이 있을 때

첫째 절의 세 수의 최댓값 명세를 만족하는 알고리즘을 쓰고, 입력 $(7, 2, 5)$ 와 $(4, 9, 9)$ 에 대해 손으로 따라가라.

풀이

$m = x$
착상: 입력을 차례로 훑으면서 지금까지 본 가장 큰 것을 변수 $m$ 에 보관한다. 첫째 단계: $m$ 에 $x$ 를 대입한다. 그 뒤 $m$ 은 지금까지 본 자료의 최댓값이며, 본 자료는 $x$ 뿐이다.
$m = \max(x, y, z)$
둘째 단계: $y > m$ 이면 $m$ 에 $y$ 를 대입한다. 셋째 단계: $z > m$ 이면 $m$ 에 $z$ 를 대입한다. 넷째 단계: $m$ 을 출력한다. 순차로 놓인 세 명령이며, 그 가운데 둘은 다른 갈래가 없는 선택이다.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
$(7, 2, 5)$ 에 대한 추적: 첫째 단계 뒤 $m = 7$ 이다. 둘째 단계에서 $2 > 7$ 은 거짓이고 $m$ 은 바뀌지 않는다. 셋째 단계에서 $5 > 7$ 은 거짓이고 $m$ 은 바뀌지 않는다. $7$ 이 출력된다.
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
$(4, 9, 9)$ 에 대한 추적: 첫째 단계 뒤 $m = 4$ 이다. 둘째 단계에서 $9 > 4$ 이므로 $m$ 의 값은 $9$ 가 된다. 셋째 단계에서 $9 > 9$ 은 거짓이고 $m$ 은 바뀌지 않는다. $9$ 가 출력되며, 이는 올바르다. 같은 값은 따로 처리할 필요가 없다.
$m \geq x, \quad m \geq y, \quad m \geq z$
정당화: 각 단계 뒤에 $m$ 은 지금까지 본 자료 가운데 하나이며, 그 가운데 어느 것도 그것을 넘지 않는다. 첫째 단계 뒤에 이는 참이고, 각 선택은 이를 유지한다. 새 자료가 더 크면 그것이 $m$ 의 값이 되고, 그렇지 않으면 그것은 $m$ 의 값을 넘지 않는다. 끝에서는 세 자료를 모두 보았으므로 $m$ 은 사후 조건을 만족한다.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
만약 $y \geq m$ 이라고 쓰고 $y > m$ 이라고 쓰지 않았더라도 결과는 같다. 같은 값일 때에는 같은 값을 대입하기 때문이다. $>$ 와 $\geq$ 가운데 무엇을 고르느냐는 최댓값의 위치도 요구할 때 중요해진다. $>$ 를 쓰면 같은 값인 위치 가운데 첫째 것이, $\geq$ 를 쓰면 마지막 것이 출력되며, 식에서는 이를 $p$ 라고 부른다.

예제 2윤년, 반례로 고치기

그레고리력에서 어떤 해는 $4$ 로 나누어떨어지면 윤년이다. 다만 $100$ 으로 나누어떨어지는 해는 제외하며, 그런 해는 $400$ 으로도 나누어떨어질 때에만 윤년이다. 한 학생이 알고리즘 “해가 $4$ 로 나누어떨어지면 예를 출력하고, 그렇지 않으면 아니요를 출력한다”를 제안한다. 이 알고리즘이 틀리는 해를 찾고, 올바른 알고리즘을 그 명세와 함께 써라.

풀이

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
명세. 입력: 정수 $n \geq 1583$ (그레고리력은 1582년 10월부터 시행되었다). 출력: 예 또는 아니요. 관계: 출력이 예인 것은 $n$ 이 $4$ 로 나누어떨어지고 $100$ 으로는 나누어떨어지지 않을 때, 또는 $400$ 으로 나누어떨어질 때이며, 오직 그때뿐이다.
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
제안된 알고리즘은 대부분의 해에서 맞으며, 그래서 올바르게 보인다. 이를 반박하려면 $100$ 으로 나누어떨어지고 $400$ 으로는 나누어떨어지지 않는 해 하나면 충분하다. $1900$ 은 $4$ 로 나누어떨어지고 알고리즘은 예라고 말한다. 그러나 $1900$ 년은 윤년이 아니었다.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
고친 알고리즘은 이어지는 세 선택으로 이루어진다. 단계 1: $n$ 이 $400$ 으로 나누어떨어지면 예를 출력하고 종료한다. 단계 2: $n$ 이 $100$ 으로 나누어떨어지면 아니요를 출력하고 종료한다. 단계 3: $n$ 이 $4$ 로 나누어떨어지면 예를 출력하고, 그렇지 않으면 아니요를 출력한다.
$2000, \quad 1900, \quad 2024, \quad 2023$
물음의 순서가 본질적이다. 가장 특수한 규칙에서 가장 일반적인 규칙으로 나아간다. 만약 먼저 $4$ 에 대해 묻는다면, $1900$ 년은 예외에 이르기 전에 예를 받게 된다. 각 경우에서 하나씩 고른 네 해에 대한 추적: $2000$ (단계 1: 예), $1900$ (단계 2: 아니요), $2024$ (단계 3: 예), $2023$ (단계 3: 아니요).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
이 교훈은 달력에만 해당하지 않는다. 알고리즘은 반례 하나로 반박되며, 반례는 흔한 경우가 아니라 규칙의 경계에서 찾는다. $2024$ , $2020$ , $2016$ 으로 시험해서는 아무것도 드러나지 않았을 것이다.

예제 3뺄셈에 의한 나눗셈은 몇 회차를 도는가

거듭된 뺄셈에 의한 나눗셈을 $a = 20$ , $b = 5$ 일 때와 $a = 0$ , $b = 7$ 일 때 손으로 따라가라. 이어서, 허용되는 모든 입력에 대해 알고리즘이 정확히 $q$ 개의 회차 뒤에 종료하고 그 출력이 사후 조건을 만족한다는 것을 정당화하라.

풀이

$20 = 5 \cdot 4 + 0$
$a = 20$ , $b = 5$ 일 때의 추적: $r$ 의 값은 $20$ , $15$ , $10$ , $5$ , $0$ 으로 바뀌고, $q$ 의 값은 $0$ , $1$ , $2$ , $3$ , $4$ 로 바뀐다. 다섯째 판정 $0 \geq 5$ 은 성립하지 않는다. 출력: $q = 4$ , $r = 0$ . 여기서 경계 경우는 나누어떨어지는 나눗셈이다. 넷째 회차는 $5 \geq 5$ 이기 때문에 일어나며, 그래서 조건은 $\geq$ 여야 하고 $>$ 이어서는 안 된다.
$0 = 7 \cdot 0 + 0$
$a = 0$ , $b = 7$ 일 때의 추적: 첫째 판정 $0 \geq 7$ 은 성립하지 않는다. 본문은 한 번도 실행되지 않는다. 출력: $q = 0$ , $r = 0$ 이며, 이는 올바르다.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
유지되는 관계. 첫 회차 전에 $b \cdot q + r = b \cdot 0 + a = a$ 이다. 매 회차마다 $r$ 의 값은 $b$ 만큼 줄고 $q$ 의 값은 $1$ 만큼 늘어나므로, $b \cdot q + r$ 의 값은 바뀌지 않는다. 따라서 이 등식은 각 회차 뒤에 성립한다.
$r_0 > r_1 > r_2 > \cdots \geq 0$
종료. 반복이 계속되는 동안 $r \geq b > 0$ 이고, $r$ 은 자연수이다. 매 회차마다 그 값은 $b \geq 1$ 만큼 줄어든다. 순감소하는 자연수의 수열은 유한하다. 반복은 종료한다.
$a = b \cdot q + r, \quad 0 \leq r < b$
종료할 때 조건은 성립하지 않았다. $r < b$ 이다. 또 $r \geq 0$ 이다. $b$ 를 빼는 것은 $r \geq b$ 일 때뿐이기 때문이다. 유지되는 관계와 함께, 출력은 사후 조건을 만족한다. 그리고 $q$ 가 회차를 세므로, 회차의 수는 몫이다.

온라인 연습

연습 1회차 세기

다음 알고리즘을 손으로 따라가고, 그것이 출력하는 값을 칸에 써라. 숫자만 쓴다.

$n$ 에 $29$ 를 대입하고, $k$ 에 $0$ 을 대입한다.
$n > 1$ 인 동안 단계 3과 4를 반복하고, 더 이상 성립하지 않으면 단계 5로 간다.
$n$ 이 짝수이면 $n$ 에 $n / 2$ 를 대입하고, 홀수이면 $n$ 에 $n + 1$ 을 대입한다.
$k$ 에 $k + 1$ 을 대입하고, 단계 2로 돌아간다.
$k$ 를 출력한다.

브라우저는 답을 즉시 검사하지만 채점하지는 않습니다.

여기에 답을 쓰세요

힌트

표를 만들어 보자. 첫 회차에 $n$ 의 값은 $29$ 에서 $30$ 으로 바뀐다. $n$ 의 값이 바뀔 때마다 한 회차로 세고, $n$ 의 값이 $1$ 이 될 때까지 계속한다.

연습 2빠진 조건

다음 알고리즘은 약식으로 쓰였으며, 거듭된 뺄셈에 의한 나눗셈의 몫과 나머지를 계산해야 하지만 반복의 조건이 빠져 있다. 밑줄이 이어진 부분을 올바른 조건으로 바꿔라. 나머지는 아무것도 바꾸지 않는다.

브라우저는 답을 즉시 검사하지만 채점하지는 않습니다.

여기에 답을 쓰세요

힌트

$a = 10$ , $b = 5$ 일 때 알고리즘을 손으로 따라가 보자. 나머지가 정확히 $5$ 여도 둘째 회차는 일어나야 한다.

연습 문제

문제마다 힌트가 있는데, 스스로 풀어 본 뒤에 여는 것이 좋다. 또 답이 있으며, 힌트를 연 뒤에 나타난다.

연습 문제 1세 수의 정렬 명세하기

문제 “세 수를 정렬하라”의 명세(입력, 출력, 관계)를 쓰고, 문제 진술이 내리지 않았던 어떤 결정을 그것이 강요하는지 지적하라. 이어서, 입력 $(5, 2, 5)$ 에 대해 명세가 두 출력 $(2, 5, 6)$ , $(2, 5, 5, 5)$ 를 배제하고, $(2, 5, 5)$ 는 받아들인다는 것을 확인하라.

힌트

“정렬된” 출력이 입력과 아무 관계가 없을 수도 있다. 반복되는 수까지 포함해 출력의 수들과 입력의 수들을 잇는 조건은 무엇인가? 오름차순인가 내림차순인가? 엄격한가 아닌가?

정답

입력: 세 수 $x$ , $y$ , $z$ . 출력: 세 수 $u$ , $v$ , $w$ . 관계: $u \leq v \leq w$ 이고, $(u, v, w)$ 는 $(x, y, z)$ 의 재배열이다. 즉 같은 값들을 같은 반복 횟수로 담고 있다. 문제 진술이 내리지 않았던 결정: 방향(여기서는 작은 것에서 큰 것으로), 순서가 엄격하지 않다는 것( $\leq$ 이지 $<$ 이 아니다. 값이 반복되면 엄격한 순서는 불가능하기 때문이다), 그리고 출력이 재배열이어야 한다는 것. $(2, 5, 6)$ 은 정렬되어 있지만 없던 $6$ 을 담고 있다. $(2, 5, 5, 5)$ 에는 값이 네 개 있다. $(2, 5, 5)$ 는 두 조건을 모두 만족한다. 재배열 조건이 없으면 $(0, 0, 0)$ 은 어떤 입력에 대해서도 올바른 출력이 될 것이다.

연습 문제 2수의 자릿수를 오른쪽에서 왼쪽으로

자연수 $n$ 을 받아 그 자릿수를 마지막 자리에서 첫째 자리 쪽으로 출력하는( $4072$ 에 대해서는 $2$ , $7$ , $0$ , $4$ 를 출력하는) 알고리즘을, $10$ 으로 나눈 몫과 나머지만 써서 번호 매긴 단계로 써라. $4072$ 와 $0$ 에 대해 손으로 따라가고, 모든 $n$ 에 대해 종료한다는 것을 정당화하라.

힌트

$10$ 으로 나눈 나머지는 마지막 자릿수이고, 몫은 그 자릿수를 뗀 수이다. 조건을 자릿수를 출력하기 전에 물을지 뒤에 물을지 정하고, 자릿수가 하나인 $n = 0$ 일 때 무슨 일이 일어나는지 보라.

정답

올바른 알고리즘의 하나: (1) $n$ 을 $10$ 으로 나눈 나머지를 출력한다. (2) $n$ 에 $n$ 을 $10$ 으로 나눈 몫을 대입한다. (3) $n > 0$ 이면 단계 1로 돌아가고, 그렇지 않으면 종료한다. 물음이 본문 뒤에 있으므로 본문은 적어도 한 번 실행된다. $n = 0$ 일 때 $0$ 을 출력하며, 이것이 그 유일한 자릿수이다. 만약 맨 앞에서 묻는다면(“ $n > 0$ 인 동안”), $n = 0$ 일 때 아무것도 출력되지 않는다. 반복이 한 번도 실행되지 않는 경우를 잊는 오류이다. $4072$ 에 대한 추적: $2$ , $7$ , $0$ , $4$ 가 출력되고, $n$ 의 값은 $407$ , $40$ , $4$ , $0$ 으로 바뀐다. 종료: 변량은 자연수인 $n$ 이다. 단계 1로 돌아간다면 $n > 0$ 이기 때문이며, $n \geq 1$ 일 때 $10$ 으로 나눈 몫은 $n$ 보다 엄격히 작으므로, $n$ 의 값은 매 회차마다 순감소한다.

연습 문제 3동전으로 거스름돈 주기

$50$ , $10$ , $1$ 단위의 동전이 개수 제한 없이 있다. 명세: 입력은 자연수 $m$ , 출력은 세 자연수 $c_{50}$ , $c_{10}$ , $c_1$ 로, $50 c_{50} + 10 c_{10} + c_1 = m$ 을 만족하고 동전의 개수 $c_{50} + c_{10} + c_1$ 이 가능한 한 적은 것이다. 어떤 사람이 다음 알고리즘을 제안한다. 이 알고리즘이 틀리는 입력을 찾고, 각 결함을 설명하고 고쳐라.

$c_{50}$ , $c_{10}$ , $c_1$ 에 $0$ 을 대입한다.
$m \geq 50$ 이면 $c_{50}$ 에 $c_{50} + 1$ 을 대입하고 $m$ 에 $m - 50$ 을 대입한다.
$m > 10$ 인 동안: $c_{10}$ 에 $c_{10} + 1$ 을 대입하고 $m$ 에 $m - 10$ 을 대입한다.
$m > 0$ 인 동안: $c_1$ 에 $c_1 + 1$ 을 대입하고 $m$ 에 $m - 1$ 을 대입한다.
$c_{50}$ , $c_{10}$ , $c_1$ 을 출력한다.

힌트

동전의 합은 언제나 $m$ 이다. 틀릴 수 있는 것은 개수이다. $10$ 의 정확한 배수와 $100$ 보다 큰 금액을 시험해 보고, 단계 2가 단계를 결합하는 어떤 방식을 쓰는지, 그리고 어떤 방식을 써야 하는지 스스로 물어보라.

정답

결함은 두 가지이다. 첫째, 단계 3은 $m > 10$ 을 쓴다. $m = 10$ 일 때 $10$ 짜리 동전은 하나도 내지 않고 $1$ 짜리 동전을 열 개 내는데, 한 개면 될 일이다. 둘째, 단계 2는 반복이 필요한 곳에서 선택을 쓴다. $m = 120$ 일 때 쓰인 그대로의 알고리즘은 $50$ 짜리 한 개, $10$ 짜리 여섯 개, $1$ 짜리 열 개(동전 열일곱 개)를 내고, 단계 3을 고친 뒤에도 $50$ 짜리 한 개와 $10$ 짜리 일곱 개(여덟 개)를 낼 것이며, $50$ 짜리 두 개와 $10$ 짜리 두 개(네 개)를 내지 않는다. 입력 $m = 100$ 은 두 결함을 모두 보여 준다. 알고리즘은 $50$ 짜리 한 개, $10$ 짜리 네 개, $1$ 짜리 열 개, 모두 열다섯 개를 내지만, 두 개면 된다. 고치는 법: 단계 2는 “ $m \geq 50$ 인 동안, …”, 단계 3은 “ $m \geq 10$ 인 동안, …”. 이렇게 고치면 알고리즘은 언제나 들어가는 가장 큰 동전을 고르며, 이 세 동전으로는 그것이 가장 적은 개수를 준다. $m$ 의 일의 자리는 $1$ 짜리 동전으로만 낼 수 있고, 남는 것은 되도록 $50$ 짜리 동전으로 내는 것이 이롭다. $10$ 짜리 다섯 개가 $50$ 짜리 한 개와 같은 값이기 때문이다. 다른 동전, 예컨대 $1$ , $3$ , $4$ 짜리로 $m = 6$ 을 낼 때에는 언제나 가장 큰 것을 고르는 방법이 더는 최소를 주지 않는다( $4 + 1 + 1$ 대 $3 + 3$ ).