BOJ - Skill) 알고리즘의 정당성 증명

  학부 알고리즘 수업 때 학기말 공부의 주된 내용은 Greedy Algorithm에서의 Proof of Optimality와 Dynamic Programming에서의 Principle of Optimality였다. 이를 국문으로 옮기면, 전자는 '정당성 증명'이라고 보면 적절하고, 후자는 '최적화 이론'이라고 보는 것이 적절하다. 약간의 어감 차이가 있는데, 쉽게 말해서 전자는 "이 알고리즘이 이러한 과정을 거쳐서 최적의 값을 낸다!"를 보이는 것이고, 후자는 "이 알고리즘이 최적의 값을 낸다면, 그 중간 과정에서도 최적의 값을 낸다!" 정도의 차이이다(물론 엄밀히 보면 보다 더 자세한 이론이 있지만).


오늘은, 이러한 알고리즘의 정당성 관련 논증에서 필요한 논증 기술들에 대해 알아보겠다. 사실 PS를 할 때에 굳이 시간도 없는데 알고리즘의 정당성을 따질 필요가 있을까 할 수 있다. 하지만, '알고리즘 문제 해결 전략 세트'의 저자 구종만씨는 다음과 같은 내용을 강조한다.

알고리즘의 정당성 증명 과정에는 해당 알고리즘을 개발하는 과정에서의 주요한 Insight(저자가 언급한 단어는 아니지만, 본인이 보았을 때 이 단어가 가장 적절)가 담겨 있다. 즉, 증명을 이해하는 과정을 거치면, 단순히 알고리즘의 Pseudo Code를 달달 외우는 것보다 훨씬 더 깊이 있는 이해를 도모할 수 있는 것이다.

  본인 역시도 이 말에 매우 동의한다. 따라서 앞으로 알고리즘 공부를 함에 있어서 증명도 결코 소홀히 넘기지 않도록 하자!라는 다짐을 해본다. 이제 알고리즘의 정당성 증명 방법들에 대해서 알아보자.

1. Mathematical Induction

  수학적 귀납법이다. 각 단계에서의 최선의 선택이 다음 단계에서의 최선의 선택으로 이어짐을 보여 알고리즘이 정당하다는 것을 증명할 수 있다.
  수학적 귀납법은 교재에 따라 다르지만, 본인은 보통 다음과 같이 두 개의 단계로 구분하는 것을 좋아한다.

0) Step Check : 이 알고리즘을 어떤 단위 단계로 나눌 수 있는지를 확인한다. 의외로 이 부분이 정말 중요하다. 코드를 기준으로 하면, 보통 반복문에서의 한 번의 순회, 또는 한 번의 재귀 호출 등을 기준으로 삼을 수 있다.

1) Basis Step : 최초 단계에서 '알고리즘이 정당한 답을 출력함'이라는 Argument가 성립됨을 보이면 된다.

2) Inductive Step : N번째 단계에서 Argument가 성립함을 가정한다. 그리고 이 Inductive Hypothesis를 이용해 N+1번째 단계에서도 Argument가 성립함을 보이면 된다.

3) Conclusion : 결론을 마무리한다.

 이러한 과정을 거쳐 알고리즘의 정당함을 보일 수 있다. 알고리즘의 (반복적인) 진행 단계가 명확히 구분되는, 또는 점화 관계가 명확히 구분되는 상황에서 유용히 사용할 수 있다. '알고리즘 문제 해결 전략 세트'에서는 반복문 불변식(Loop Invariant)라는 개념을 도입해 이를 더 확장해 설명하고 있지만, 이는 귀납법의 또 다른 표현 방법에 불과하다 느껴 굳이 더 내용을 기재할 필요는 없다고 느껴 생략하겠다.

2. Contradiction

  모순을 보여 논증을 진행하는, 귀류법을 말한다. 귀류법은 보통 "A이면 B이다."라는 상황에서 A를 반대로 가정해 B가 아니라 모순으로 이어짐을 보이는 방법으로 수행할 수 있다. 이러한 귀류법은 알고리즘이 최선(Optimal, 최단 경로, 최고점 등)을 도출함을 보일 때 유용히 사용할 수 있는데, 그 Idea는 다음과 같다.

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 보여, 우리가 원하는 상황이 곧 정당한 상황임을 보이는 것이다.

  이러한 귀납법과 귀류법은 다양한 알고리즘의 적용 과정에 있어서 정석적인 형식으로 사용하진 않더라도 Informal한 형태로 수행하여, 우리가 작성하고 있는, 사용하고 있는 알고리즘이 주어진 문제 상황에서 정답을 이끌 것임을 확인하는데 쓰일 수 있다.

3. Pigeonhole Principle

  학부 이산수학 수업에서 이 비둘기집의 원리를 깊게 공부했던 기억이 난다. 매우 당연하게 느껴지는 서술임에도 불구하고 매우 중요한 의미를 지니고 있다. 다들 알고 있겠지만, Hole의 개수보다 Pigeon의 개수가 더 많으면 반드시 최소 하나의 Hole에는 복수의 Pigeon이 들어있을 것이라는 이론이다. 이 역시 좀 더 세부적인 유형으로 Theorem이 갈리는데, 솔직히 이 정도만 이해하고 있어도 충분하다.

  특정한 문제 상황, 특히나 경우의 수와 관련한 문제 상황에서 간혹 (아니, 상당히 자주) 이 비둘기집의 원리를 이용해 정당성을 증명할 수 있다.

4. Constructive Proof

  '답이 존재하는가'에 대한 대답으로 '이렇게 만들면 답이 존재하게 된다.'라고 하는 것이 바로 구성적 증명이다. 즉, 답이 존재하는 이유를 보여주는 것이 아니라, 답을 만들어내는 과정 그 자체를 제시하는 증명인 것이다. 따라서 우리가 평시 사용하던 증명과는 조금 뉘앙스가 다르다. 약간 알고리즘의 증명이 곧 알고리즘의 설명과 같은 형태를 띈다. 이 역시 간혹 나타나는 증명 기술이다(대표적으로 Stable Matching Problem).

 이때, '알고리즘이 반드시 종료함', '알고리즘의 우리가 원하는 답을 만들어냄'을 각각 증명해야하는데, 그 과정에서 귀류법, 귀납법 등이 사용될 수 있다. 자세한 내용은 '알고리즘 문제 해결 전략 세트'에서 소개하는 'Stable Marriage Matching Problem'의 Constructive Proof 소개란에서 확인할 수 있다.