알고리즘의 정당성 증명

1. 수학적 귀납법

가장 유용하게 사용되는 방식. 대부분의 알고리즘이 반복적인 요소를 가지고 있기 때문이다.

  1) 단계 나누기 : 증명하고자 하는 문제를 여러 단계로 나눔.

  2) 첫 항 증명 : 첫 번째 단계가 참인지를 증명

  3) 귀납 증명 : 첫 번째가 참이면 N번째 단계도 참인지를 증명

2. 반복문 불변식

반복문의 내용의 중간 결과가 어떠한 경우에도 우리가 원하는 답으로 가는 길 위에 있는지 명시하는 조건

  1) 반복문 진입 전 불변식이 성립함을 증명

  2) 반복문 내용이 불변식을 깨뜨리지 않음을 증명

  3) 반복문 종료 시 불변식이 성립하면 정답을 구한 것임.

3. 귀류법

원하는 상황과 반대의 경우를 가정하고 논리를 전개하여 결론이 잘못되었음을 증명하는 방법.