고양이 두 잔

완전 탐색이란 컴퓨터의 성능을 믿고 모든 경우의 수를 다 체크하는 방법이다. 상대적으로 구현이 간단하고, 해가 존재한다면 반드시 찾을 수 있는 방법이기도 하다. 예를 들어 숫자 4자리로 구성된 자물쇠의 암호를 푼다면, '0000'부터 '9999'까지 다 넣어보는 방식이다. 당연하게도 최적의 솔루션을 제공해주지 않으며, 때문에 다음 두 상황에 주로 쓰인다. 적용 가능한 다른 알고리즘이 없을 때 복수의 솔루션을 확인해야 할 때 예를 들어 책 한 권이 주어지고 그 책에서 '고양이'라는 단어를 찾아야 한다고 가정해보자. 책은 당연하게도 단어들이 정렬되어 있지 않으므로 처음부터 끝까지 단어를 비교하는 수밖에 없다. 이럴 때 사용되는 것이 완전 탐색 알고리즘이며, 이 경우 시간 복잡도는 O(n)이다. 계속해서 완전..