1장 개미 수열 시작하기
9번째 줄에 나올 수는 무엇인가?
1
11
12
1121
122111
112213
12221131
1123123111
?
답은 12213111213113이다. 이 수열은 ‘개미 수열’1이라고 알려져 있으며, 앞 줄을 읽어서 다음 줄을 만들어낼 수 있는 무한 수열이다. 위 문제에서 마지막 줄을 “1이 2개, 2가 1개, 3이 1개, …” 처럼 읽을 수 있고, 따라서 “122131…” 의 결과를 얻게 된다.
개미 수열의 n번 줄 출력하기. 이 책이 풀고자 하는 문제다.
읽고 말하기 수열
개미 수열은 본래 ‘읽고 말하기 수열(look-and-say sequence)’이라고 한다. 읽고 말하기 수열은 다음과 같이 전개된다.
1
11
21
1211
111221
수열이 만들어지는 규칙은 이미 설명한 대로다. 하지만 영어로 읽어야 한다. 다섯 번째 줄을 영어로 읽는 다면 “three 1s, two 2s, then one 1”이 되어 그 다음 줄 “312211”을 얻을 수 있다. 하지만 앞서 소개한 개미 수열은 이것과 조금 다르다.
1
11
12
1121
122111
우리는 “세 개의 1” 대신 “1이 세 개”처럼 읽으므로 수열의 형태가 바뀐 것이다. 재미있게도 이 수열은 읽는 방식을 뒤집는다 해도 전체적으로 영향을 받지 않고 단지 각 줄이 뒤집어질 뿐이다. 수열 본래의 특성이 그대로 유지된다.
우리나라에서는 읽고 말하기 수열보다는 각 줄이 뒤집어진 개미 수열이 더 유명하다. (우리에게 더 자연스러운 뒤집어진 수열은 분명 본래의 읽고 말하기 수열과는 다른 수열이다.) 이 두 수열을 구분지어 부를 수도 있겠지만, 이 책에서는 길이를 먼저 말하는 영어식 표현의 수열을 중심으로 다룰 것이다.
Java #0 - for와 String
개미 수열 문제를 푸는 첫 번째 프로그램을 살펴보자. 아래 Java 코드는 개미 수열의 10번 줄을 출력한다. (이제부터는 0번 줄을 첫 줄로 본다.)
public class LookAndSay {
public static void main(String... args) {
String s = "1";
for (int line = 0; line < 10; line++) {
int length = 1;
char head = s.charAt(0);
String result = "";
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == head) {
length++;
} else {
result += length;
result += head;
length = 1;
head = s.charAt(i);
}
}
result += length;
result += head;
s = result;
}
System.out.println(s);
}
}
첫 줄 “1”을 시작으로, 다음 줄의 계산을 반복한다. 다음 줄을 계산하는 방법은 앞 줄의 글자를 하나씩 읽으면서 이미 읽은 글자와 같으면 길이(length)를 증가시키고 그렇지 않으면 지금까지 읽은 글자의 길이와 그 글자(head)를 결과에 누적시킨다.
아름다운 코드가 아니어서 실망할지도 모르겠다. 하지만 개미 수열의 10번 줄을 출력하는 완벽한 프로그램이다. 이 코드의 목적은 이 책을 읽는 모두가 개미 수열 문제의 규칙을 완전히 이해할 수 있도록 돕기 위한 것이다. 이 코드는 앞으로 만들어나갈 다양한 변형의 중요한 베이스라인이 되어줄 것이다.
Haskell #0 - 리스트
단순한 문제에 단순한 코드를 보고 실망하신 분들을 위해 조금 난해한 코드를 하나 보여주겠다. 관심을 가지고 이 책을 계속 읽어나가는 데 조금이나마 도움이 되기를 바란다. 아래는 Haskell로 작성한 개미 수열 프로그램이다.3 Java 프로그램과 마찬가지로 10번 줄을 출력한다.
import Data.List
import Control.Monad
ant = iterate (group >=> sequence[length, head]) [1]
main = print (ant !! 10)
이 프로그램은 ant, main 두 함수를 정의한다. ant 함수는 개미 수열을 리스트로 나타내고, main은 개미 수열의 10번 줄(!! 10)을 출력한다. ant 함수는 첫 줄(1 하나로 된 리스트 [1])을 시작으로 다음 줄 계산(group >=> sequence[length, head])을 반복(iterate)한다. 다음 줄을 계산할 때는, 앞 줄 리스트를 같은 값끼리 묶고(group), 각 그룹의 길이(length)와 머릿값(head)으로 된 리스트로 바꿔치운다.(>=> sequence[length, head])
Java 코드와 Haskell 코드는 본질적으로 같은 일(10번 줄 출력하기)을 하면서도 동작의 차이는 엄청나다. 이 책을 통해 Java나 JavaScript로도 그 차이를 극복할 수 있을 것이다.
Java #1 - ant()와 next() 분리
이미 보여준 Java 코드는 main()에 모든 내용이 들어있어서 뭔가 이야기를 이어가기가 어려우니 조금만 리팩터링을 해 놓자.
ant()와 next()로 분리 (Java)private static String ant(int n) {
String s = "1";
for (int line = 0; line < n; line++) {
s = next(s);
}
return s;
}
private static String next(String s) {
int length = 1;
char head = s.charAt(0);
String result = "";
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == head) {
length++;
} else {
result += length;
result += head;
length = 1;
head = s.charAt(i);
}
}
result += length;
result += head;
return result;
}
ant(n) 함수는 개미 수열의 n번 줄을 계산하는 함수고, next(s) 함수는 앞 줄을 읽어 다음 줄을 계산하는 함수다.
Wishful Thinking
일단 동작하는 main()을 만들고, 여기서 ant()를 Extract하고, 다시 여기서 next()를 Extract하였다. 또다른 접근법은 Wishful Thinking이란 것인데, “이런 것이 있다면…” 이란 가정으로 코드를 만들어가는 방법이다.4 잘 익히고 사용하면 매우 유용한 방법이다.
어떤 클래스가 있다면, 어떤 메쏘드가 있다면, 어떤 변수가 있다면… 이런 순간마다 필요로 하는 요소를 추가하기 위해 다른 위치로 점프하는 것은 사고의 흐름을 끊어버린다. 대신, 현재 그런 클래스나 메쏘드가 없다고 하더라도 흐름을 끊지 않고 마치 이미 다 준비되어 있는 것처럼 진행하는 방법이다.
마치 ant()가 이미 있는 것처럼 아래와 같이 작성한다.
System.out.println(ant(10));
ant(10)에 빨간불이 들어올 것이다. IDE의 자동 완성 기능은 멋지게 ant()함수의 기본 골격을 만들어 준다. 다음 줄을 계산하는 next()라는 함수가 있다면(물론 아직 만들지 않았다), ant()는 이를 n번 호출하면 된다.
String ant(int n) {
String s = "1";
for (int i = 0; i < n; i++) {
s = next(s);
}
return s;
}
다시 next(s)에 빨간불이 들어올 것이다. 자동 완성 기능으로 next()의 뼈대를 만든다. 처음부터 이런 방법으로 작업했다면 next()는 앞 절의 코드보다 훨씬 더 간결하고 읽기 쉬운 코드였을 것이다.