[알고리즘] 정당성 증명 - 수학적 귀납법

이진이·2023년 8월 10일

feet. 반복문 불변식, 귀류법, 비둘기집 원리

알고리즘의 정당성 증명

알고리즘을 시작하기에 앞서 알고리즘의 정당성 증명이라는 것을 알아야 한다. 말 그대로 알고리즘을 증명하는 것이다. 우리가 머리로 생각한 알고리즘이 실제로 정확하게 잘 돌아간다고 보장할 수 없기 때문에 정당성을 입증해야 한다.

명제

수학적 증명을 위해서 명제를 기억해내야 한다. 부끄럽게도 고딩때 배운 건 다 까먹었다.😳

명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다. 두 조건 $P, Q$ 가 있을 때 " $P$ 이면 $Q$ 이다."가 명제이다. 기호로는 $P→Q$ 로 나타낸다. 여기서 오늘 배울 "증명"에 있어서 중요한 문제가 있다. 바로 Vacuous이다.

Vacuous는 "P이면"이라는 것이 애초에 거짓인 상태이다. 이건 예를 들어야 이해가 쉽다. 나는 1시 이전에 점심을 먹는다.
$P$ 가 "1시 이전이면"이고, $Q$ 가 "점심을 먹는다."라고 하자.

아직 1시가 되지 않았으면 $P$ 는 True이다. 이때 밥을 먹으면 $Q$ 도 Ture이므로 $P→Q$ 도 True이다. 밥을 안 먹으면 $Q$ 가 False이고, $P→Q$ 도 False이다.
그런데 1시가 지났다고 하자. 즉, $P$ 는 False이므로 Vacuous상태이다. 이때 내가 밥을 먹었으면 $Q$ 는 True인데, $P→Q$ 는 뭘까? 1시가 지났다고 내가 밥을 먹으면 안 되는 것인가? 또, 내가 밥을 먹지 않았으면? 점심시간이 이미 지났는데 점심을 먹지 않았다고 해서 False라고 할 수 있을까?

Vacuous일 때 $Q$ 가 무엇이든, $P→Q$ 가 False라고 할 수 없을 것이다.

$P$ (⏰)	$Q$ (🍴)	$P→Q$ (⏰🍴❓)
True	True	True
True	False	False
False	True	😋
False	False	😢

대신 1시 이후엔 밥을 먹든, 안 먹든 내 마음이니까 True라고 해야 한다. 즉, P의 조건을 벗어나면 뭘 하든 맞다고 해줘야 되는거다. 이렇게 Vacuous 일때는 명제의 답이 항상 True가 된다.

수학적 귀납법

명제를 배웠으니 귀납법을 배우자. 수학적 귀납법은 조건 $P(n)$ 이 모든 자연수 n에 대하여 참인지 거짓인지 판별하는 것이다. 수학적 귀납법의 기본형은 다음과 같다.

1. Base : $P(1)$ 이 참이고,

2. Step : $P(n-1) → P(n)$ 이 참이면,

3. Result : $P(n)$ 은 모든 자연수 n에 대해서 참이다.

Base와 Step을 각각 증명해서 나중에 합치면 Result가 된다.

에를 들어

$P(n) = n > 0$ 일때

Base : $P(1)$ 은 $1 > 0$ 이므로 True

Step : $P(n-1) → P(n)$ 은 $(n-1 > 0) → (n > 0)$ 이다.

Proof of step :

$a > 0$ 이고 $b > 0$ 이면, $a+b > 0$ 이다. (axiom)
$n -1 +1 = n$
a에 n-1을, b에 1을 대입하면 2번에 따라 $n-1+1 = n$ 이므로, $n > 0$ True

Result : 모든 자연수 n에 대해 True

수학적 귀납법으로 재귀 알고리즘 증명

필요한 건 다 배웠다. 수학적 귀납법으로 증명할 수 있는 재귀함수를 직접 증명해보자.

int sum(int x){
	if (x <= 0) return 0;
    return x + sum(x-1);
}

$\sum_{n=1}^{x}{n}$ 즉, 1부터 n까지의 합을 구하는 코드이다. 직관적으로 보면 다음과 같다.

출처

이제 이걸 증명하자. ${sum}(x)$ 은 항상 $\sum_{n=1}^{x}{n}$ 를 리턴한다.

Base : ${sum}(1)$ 은 1을 리턴한다. True

Step : ${sum}(x-1)$ 이 $\sum_{n=1}^{x-1}{n}$ 을 리턴하면, ${sum}(1)$ 는 $\sum_{n=1}^{x}{n}$ 를 리턴한다.

이제 여기서 Vacuous의 개념을 다시 생각해보자. Vacuous일 때는 항상 True이므로 증명할 필요가 없어진다. 즉, $P(n-1)→P(n)$ 에서 $P(n-1)$ 이 이미 거짓이면 $P(n)$ 은 논의할 의미가 없어진다. 때문에 귀납법에서는 Vacuous 상태는 없다고 치고! == $P(n-1)$ 을 항상 True라고 치고!! $P(n)$ 만 증명하면 된다는 거다.

따라서 ${sum}(1)$ 가 $\sum_{n=1}^{x}{n}$ 를 리턴하는지만 확인하면 되는데,
${sum}(1)$ 는 $x+{sum}(1)$ 를 리턴한다고 코드에 쓰여 있으므로 ${sum}(1)$ 는 $\sum_{n=1}^{x}{n}$ 를 리턴하는 것이 증명되었다.True

Result : 따라서 $sum(n)$ 은 모든 자연수 n에 대해서 참이다.

반복문 불변식

위의 증명처럼 알고리즘은 대부분 반복적인 요소를 가진다. 이때 귀납법을 이용하여 반복문의 정당성을 증명하는 것이 반복문 불변식이다. 반복문 불변식이란, 반복문의 내용이 실행될 때마다 중간 결과가 원하는 답으로 잘 가는지 판별할 수 있는 조건식이다.

무슨 소리냐고? 답을 찾기 위해 관여하는 변수(또는 객체)들이 조건문 안에서 값이 변해가면서 내가 원하는 답의 범위를 넘어가거나, 예외를 발생시키는지 등을 확인하기 위해서 만드는 조건을 담는 식이다. 아주아주 간단한 예를 들면, 반복문 안에서 배열을 사용하고, 배열을 꺼내올 인덱스 값을 변수 i 로 사용했을 때, i는 반복문을 반복하며 0 미만, 배열의 길이 이상이 되면 안된다. 이때 "불변식 : $-1 < i <arr.length$ "라고 할 수 있다.