알고리즘의 4가지 정당성 증명방법

학부생이 개인의 관점에서 정리한 정보를 담는 블로그입니다. 

저를 100% 신뢰하지 말아주시길 부탁드립니다. (한 85% 정도?)

알고리즘을 공부할 더 정확한 길은 많습니다 ... (구종만님의 알고리즘 문제 해결 전략, 다양한 책들 ...)

심지어 수정 예정인 글입니다.

 

알고리즘을 왜 써야 하나요?

: 우리가 풀고 싶은 문제 A가 있습니다. 물론 우리가 자체의 해결 방법을 고안해 내어 해결한다면 정말 즐거운 일 일것입니다. 하지만 보통의 경우에 이는 굽이굽이 돌아가는 길입니다. 왜냐하면 이미 수백 혹은 수천년 전에 (우리보다 훨씬) 똑똑하고 유명한 누군가가 고안해낸 "문제 A를 푸는 방법"이 존재하기 때문입니다. 그 방법을 우리는 "알고리즘"이라고 부릅니다. 그 오랜 시간동안 많은 사람들이 인정해온 방법이니 그 알고리즘은 꽤나 믿을만한 방법이겠죠. 또 문제 A를 푸는데 꽤나 적합한 방법일것입니다. 

 

증명을 왜 해야하죠?

: 그 알고리즘이 정확하다고 100% 믿을 수 있나요? 믿겠다면 아쉬운 일이지만 ... 대부분의 경우에는 증명하지 않으면 "제대로" 이해했다고 하기가 힘듭니다. 적어도 저는 증명을 스스로 했을때와 하지 않았을 때, 알고리즘에 대한 이해도가 달랐습니다. 왠만하면 스스로 정확한지 확인하고 쓰자 ... 는 것이죠. 또 혹시 언젠가 내가 알고리즘을 고안해 냈는데, 내 알고리즘의 정확성을 증명하기가 막막하다면 ... 아주 슬플 것입니다. 

 

예. 그래서 알고리즘을 증명하는 방법에 대해 알아보겠습니다. 

The Proof of Correctness 라고 칭합시다. 정확성에 대한 증명. (그리디의 정당성 증명, DP의 최적화 이론이라고 나누어 지는듯합니다. 하지만 잘 알지 못하므로 생략하겠습니다. 원하신다면 조사하셔서 저에게도 살짝 ... )

 

1. 수학적 귀납법 (Induction)

수학적 귀납법에 의한 증명. 학창시절에 많이 들어 본 증명 방법일 것입니다. (P(n)이 모든 정수에서 성립함을 보이기 위한 증명 방법으로 배웠을 것입니다.)

 

https://inst.eecs.berkeley.edu/~cs170/fa14/tutorials/tutorial1.pdf

이 링크의 과정에 따라 설명하겠습니다. 

 

step 1. Inductive 가설을 구성하라. (이 가설은 loop invariant가 된다.)

-> "알고리즘이 항상 만족할 가설을 세우자"

-> "모든 루프에 대해서 이 알고리즘은 이 가설을 만족할 것이다."에서 [가설]을 최대한 명백하게 정의해야 한다. 

>> This is always true! 라는 소리가 절로 나오는 가설을 정의해야 한다. 

그리고 그것이 우리의 [Loop Invariant]가 된다. 

 

step 2. Loop Invariant가 재귀(inductive) 임을 증명하자.

-> 재귀로서 증명하는 방법은 일반적으로 base에서 증명, step에서 증명이다.

---> 즉, n = 0일때 성립함. (base)

---> P(i) 가 참일때, P(i+1)이 참임을 증명. (step)

----->> 모든 정수(경우)에서 참임을 알 수 있다. 

이때, step 과정에서 P(i)가 거짓일 때는 vacuously true 이므로 P(i+1)이 참인지 아닌지에 관계없이 항상 step이 참이다.

즉, 우리는 P(i)가 참일 경우에 P(i+1)이 참이 되어 P(i) -> P(i+1)이 참이 되는지 만을 검사하면 되는 일이다. 

(초반에 이 부분에 대한 이해가 참 까다롭다.)

 

증명을 해야하는 입장에서 덧붙이자면, step을 증명하는 과정에서는

[""어떤 상황이 발생하더라도"" invariant를 만족한다.] 를 보이기 위해 case들이 마구마구 나뉘어진다. 

발생할 수 있는 모든 경우에서 만족함을 보이기 위해 애써보자. 

 

step 3. Loop Invariant를 이용하여 정확성을 증명하자. 

-> 그 invariant가 과연 정말 정확한지에 대해 검사한다. Loop terminate 과정, 즉 loop가 끝나고 난 이후의 과정을 살핀다고 보면 될 것이다. (이 부분은 정확하지 않다. 추후 점검 후 추가할 예정이다.)

 

>> [나의 개인적인 의문점]

: Invariant 와 Induction 의 차이점에 대해 오랜시간 헤맸다. 

지금와서 보니 Invariant ⊆ Induction으로 보인다. Induction의 진행 과정 중에 Invariant 가 포함되어 있다고 이야기할 수 있을까?

Loop Invariant는 세가지 (초기, 유지, 종료) 단계에서 가설을 항상 만족하는 것을 보여서 증명. Induction은 base와 step, P(n) -> P(n+1) 이 참임을 보임으로써 모든 단계에서 항상 가설을 만족하는 것을 보이는 증명.

비슷한 과정이지만, 둘은 별개의 단독의 증명 방법이려나 ... 잘 모르겠다. 

 

2. Contradiction

: 모순을 보여서 논증을 진행하는 귀류법을 말한다. 

초기의 가정의 반(반대)에서 시작하고, 그 과정에서 모순이 발생함으로써 원래 초기 가정이 참임을 보이는 증명 과정이다. 

자주 본 증명 방법이므로 넘어가자. 

 

3. Pigeonhole Principle 

hole 개수보다 piegeon의 수가 더 많으면, 적어도 하나의 홀에는 piegeon이 복수의 수가 들어간다는 것이다. 

경우의 수와 관련하여 많이 사용한다고 하는데 ,,, 나는 아직 Pumping Lemma에서만 만날 수 있었다. 

아직 이 증명 방법으로 다양한 문제를 풀어보지 못했어서, 소개할 만큼 이 증명 방법과 친밀하지 못하다. 

 

4. Constructive Proof 

: 내 기준 가장 재미있는 증명 방법이다. 

A가 정말 돼?라고 물어본다면, 봐바 ~ 이렇게 해보니까 돼! 이렇게 만들 수 있는데, 이렇게 만들면 돼! 라고 보여줌으로써 증명하는 방법이다. 

실제로 만들어 졌는데, 그것이 참이 아닐 수가 없는 것이다. 

 

 

다음 포스팅에서 몇몇 알고리즘에 대한 증명을 해볼 것이다.