Algorithm/종만북 뽀개기

알고리즘의 정당성 증명 해결해야 할 문제가 간단할 때는 직관적으로 알고리즘을 설계할 수 있지만, 문제가 복잡해지면 알고리즘이 과연 문제를 제대로 해결하는지 파악하는 것이 힘들다. 물론 단위테스트를 통해서 해결할 수도 있겠지만, 이 방법으로는 턱없이 모자라다. 따라서, 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘에 대한 증명은, 알고리즘을 유도하는 데 결정적인 통찰을 담고 있다. 모든 알고리즘은 치열한 고민과 개선 과정을 거쳐 태어나고 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨있는 경우가 많다. 또한, 증명을 아는 편이 사용하는 입장에서도 큰 공부가 된다. 1. 반복문 불변식 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법이다. 대부분의 알..