Algorithm/종만북 뽀개기

1. 무식하게 풀기공부를 할수록 우아한 답안을 만들고 싶은 마음이 커진다. 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽다. 이런 실수를 방지하기 위해서 '무식하게 풀 수 있을까?' 라는 생각을 해보아야한다. "brute-force(무식하게 푼다)"컴퓨터의 빠른 계산 능력을 이용해, 가능한 경우의 수를 일일이 나열하며 답을 찾는 방법을 의미한다.이런 알고리즘을 완전 탐색(exhaustive search)라고 한다.  2. 재귀 호출과 완전 탐색컴퓨터가 수행하는 많은 작업들은 대개 작은 조각으로 나눌 수 있다.범위가 작아지면 작아질 수록 각 조각의 형태들은 유사해진다.이러한 작업을 구현할 때 유용하게 재귀 함수(recursive function)/재귀 호출(recursion..

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