더북(TheBook)

두 단계로 돌아가는 알고리즘으로 이 문제를 효율적으로 풀 수 있다. 첫 번째 단계는 표현 변경 단계로, 단어를 이루는 글자들을 정렬해 단어마다 “서명”을 할당한다. 그 다음은 인스턴스 단순화 단계로, 파일을 서명의 알파벳 순서로 정렬한다(데이터 정렬은 인스턴스 단순화의 특별 케이스다). 그러면 애너그램들은 연속된 순서로 자리한다.

연습 삼아 같은 개념을 활용하는 수 배치 퍼즐(2.043)을 풀어보는 것도 좋겠다.

또 다른 표현 변경의 예로 문제의 입력을 이진수 또는 삼진수로 표현하는 방식이 있다. 진법 개념을 잘 모르는 사람을 위해 간단히 설명하면 이렇다. 지난 800여년 동안 대부분의 사람들이 사용해온 십진법에서는 정수를 10의 거듭제곱을 결합한 형태로 표현한다. 예를 들어 1069 = 1·103 + 0·102 + 6·101 + 9·100이다. 이진법, 삼진법에서는 정수를 각각 2와 3의 거듭제곱을 결합한 형태로 표현한다. 예를 들어 106910 = 100001011012이다. 1069 = 1·210 + 0·29 + 0·28 + 0·27 + 0·26 + 1·25 + 0·24 + 1·23 + 1·22 + 0·21 + 1·20이기 때문이다. 그리고 106910 = 11101213인데 1069 = 1·36 + 1·35 + 1·34 + 0·33 + 1·32 + 2·31 + 1·30이기 때문이다. 십진법에서는 열 개(0부터 9까지)의 숫자를 사용하지만 이진법에서는 두 개(0과 1), 삼진법에서는 세 개(0, 1, 2)만 사용한다. 모든 십진 정수를 이진법과 삼진법에서 각각 유일한 수로 표현할 수 있는데 그 수는 각각 2와 3으로 반복해 나눠 구할 수 있다. 특히 이진법은 컴퓨터로 구현할 때 가장 간편한 방법이므로 매우 중요하다.

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