알고리즘 증명

알고리즘 증명

알고리즘을 설계했다면 알고리즘이 제대로 동작하는지 증명할 필요가 있다. 단위 테스트를 이용해 여러 개의 입력에 대해 프로그램을 실행해 보고 그 답을 점검할 수도 있지만, 이런 식으로는 이 알고리즘이 가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 이번 글에서는 알고리즘 증명을 위해 흔히 사용하는 기법들을 소개한다.

수학적 귀납법과 반복문 불변식

수학적 귀납법은 자연수 n과 관련된 명제 P(n)이 모든 자연수에 대해 성립한다는 것을 증명하는 방법이다. 증명은 아래의 두 단계로 구성된다.

1. P(1)이 성립함을 보인다.
2. P(n)이 성립한다 가정하에 P(n+1) 또한 성립함을 보인다.

수학적 귀납법의 원리는 도미노와 같다. 다음 2가지 사실을 보이면 모든 도미노가 쓰러진다는 걸 직관적으로 알 수 있는 것과 같이 명제 P(n)이 모든 자연수에 대해 성림됨을 알 수 있다.

1. 첫 번째 도미노를 쓰러트린다.
2. 한 도미노가 쓰러지면 다음 도미노 역시 쓰러진다.

수학적 귀납법을 알고리즘에도 사용할 수 있다. 거의 모든 알고리즘이 반복적인 구조를 가지기 때문이다. 귀납법으로 알고리즘을 증명할 때 반복문 불변식(loop in-variant)을 사용하는데 반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 정답으로 가는 길 위에 있는지 명시하는 조건이다. 항상 변하지 않는 조건이기에 불변식이라 부른다. 반복문 불변식을 이용해 아래와 같이 알고리즘을 증명한다.

1. 반복문 진입시에 불변식이 성림함을 보인다.
2. 반복문 내용이 불변식을 깨드리지 않음을 보인다. 즉 반복문 마지막에서 불변식이 성립함을 보인다.

//(1)불변식이 성립함을 보인다.
while(조건) {
	//반복문 내용 시작
    		...
    //반복문 내용 끝
    //(2)불변식이 성립함을 보인다.
}

처음 불변식이 성립하고 반복문에서도 불변식이 성립함을 보인다면 이 알고리즘은 계속해서 불변식을 성립함을 알 수 있다. 때문에 알고리즘이 올바른 답을 도출해낼거라 증명할 수 있다. 이를 위해선 중간 계산 결과가 항상 정답으로 가는 길에 있는지 체크하는 불변식을 잘 작성할 필요가 있다.

귀류법

귀류법이란 P이면 Q이다 라는 명제에서 그 명제의 결론 부분을 부정함으로써 생겨나는 귀류 명제(P이면 Q가 아니다)의 모순을 보임으로써 간접적으로 원래의 명제가 참임을 증명하는 방법이다. 

 

쉽게 말해 나는 사람이다 라는 명제가 있다면 원래 명제(나는 사람이다)와 귀류 명제(나는 사람이 아니다) 중 한 가지는 참이며 나머지 한 가지는 거짓이다. 나는 사람이면서 사람이 아니다라는 명제는 말이 되지 않기 때문이다. 이때 귀류 명제가 거짓임을 증명한다면 간접적으로 원래 명제가 참임을 알 수 있다.

 

귀류법은 대개 어떤 선택이 항상 최선임을 증명하고자 할때 많이 이용된다.

비둘기집의 원리

비둘기집의 원리는 다음과 같다. 10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 존재한다.

 

매우 당연하게 느껴지는 비둘기집의 원리는 이곳저곳에서 유용하게 쓰인다. 예를 들어 최대 만개 길이의 문자열을 받아 1부터 100까지의 정수를 리턴하는 해시 함수가 있다면 해시 충돌이 무조건 발생함을 비둘기집의 원리를 통해 증명할 수 있다.