수학적 귀납법 "반복적인 구조를 갖는 명제를 증명하는 데 유용하게 사용되는 증명 기법" 귀납법 증명은 크게 세 단계로 나누어진다. (1) 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다. (2) 첫 단계 증명 : 그중 첫번째 단계에서 증명하고 싶은 내용이 성립함을 보인다. (3) 귀납 증명 : 첫번째 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다. 반복문 불변식 귀납법을 통해 알고리즘의 정당성을 증명할 때, 가장 유용하게 사용되는 개념이다. 반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 반복문이 마지막 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 하는 것이다. 반..