더북(TheBook)

1.1 알고리즘 설계를 위한 일반 전략

이 튜토리얼은 알고리즘을 설계하기 위한 몇 가지 일반 전략을 간단하게 살펴볼 수 있도록 만들었다. 이 전략을 모든 퍼즐에 적용할 수는 없겠지만 여러 전략을 전반적으로 익혀 두면 오랫동안 요긴하게 써먹을 수 있다. 여기에 나온 전략들은 컴퓨터 공학 분야의 문제를 푸는 데도 활용될 수 있다. 따라서 이 전략들을 퍼즐에 적용하는 법을 배우다 보면 컴퓨터 공학 분야의 문제 해결법도 익힐 수 있을 것이다.

하지만 주요 알고리즘 설계 전략을 살펴보기 전에 알고리즘 퍼즐의 두 가지 유형을 짚고 넘어가야겠다. 모든 알고리즘 퍼즐에는 입력이 있다. 입력은 퍼즐의 인스턴스를 정의하는 역할을 한다. 인스턴스는 (“저울로 여덟 개 동전 중 가짜 동전을 찾아내라”와 같은 문제에서처럼) 구체적으로 주어지거나 (“저울로 n개 동전 중 가짜 동전 하나를 찾아내라”와 같은 식으로) 일반적으로 주어질 수 있다. 특정 퍼즐의 특정 인스턴스만 푸는 경우라면 주어진 인스턴스만 풀면 된다. 사실 같은 퍼즐도 다른 인스턴스에 대해서는 풀이법이 다르거나 아예 없을 수도 있다. 반대로 퍼즐에서 주어진 특정 숫자가 별 의미가 없는 경우도 있다. 이럴 때는 일반적인 경우에 대해 퍼즐을 풀어내는 것이 더 보람 있을 뿐만 아니라 때로는 더 쉬울 수도 있다. 하지만 퍼즐이 특정 인스턴스 형식으로 주어졌든 일반화된 형식으로 주어졌든 처음에는 몇 가지 간단한 인스턴스를 먼저 풀어보는 것이 바람직하다. 그 과정에서 엉뚱한 길로 샐 가능성도 있지만 보통 주어진 퍼즐을 더 잘 파악하는 데 도움이 된다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.