누워서 읽는 알고리즘

 이 책을 정말로 누워서 읽지는 않았지만, 지하철 안에라던가 가볍게 시간을 때울만한 짬이 났을 때 정말 가볍게 알고리즘을 읽기에 좋은 책이었다. 그렇다고 이 책 안에 있는 내용들이 결코 가볍다는 것은 아니다. 다만 이야기처럼 다양한 알고리즘들에 대해 풀어내는 형식이었다. 알고리즘은 흥미진진한 수수께끼를 푸는 과정과 일맥상통하다. 또한 알고리즘을 개발한 다양한 천재들도, 그러한 관점에서 알고리즘을 접근했다는거다. 그리고 이 책을 읽으면서 저자가 공대적인 유머를 하나씩 던지는데 그런 내용도 정말 재미있게 읽었다.

p.43

 같은 팀 내에 비네이가 둘이 있는데, 하루는 비네이가 팀원들에게 다음과 같은 이메일을 보냈다.

 

 Team, (팀원 여러분)

Vinay just called me and said he is off today because he didn't feel well.

(비네이가 방금 전화를 해서 말하기를 몸이 좋지 않아서 오늘 쉰다고 합니다.)

 Vinay(비네이)

 

 그래서 필자는 답장으로 보내면서 비네이에게 빨리 낫기를 바란다는 말을 한 뒤에 다음과 같은 내용을 덧붙였다.

 

Your email is so recursive that I am worried about a stack overflow error.

(네 이메일은 너무나 재귀적이라서 스택 오버플로우 오류가 날까 걱정이 된다.)

팰린드롬 알고리즘

 팰린드롬이란 madam 과 같이 단어가 대칭적인 것을 말한다. 숫자의 경우 121, 4884 와 같은 숫자들을 말한다. 이 때의 이슈는 87과 같은 수를 팰린드롬의 수로 만들어보자는 것이다. 팰린드롬의 알고리즘은 다음과 같다.

 

원래의 수 와 원래의 수를 뒤집은 수를 더하는 과정을 반복하는 것이다.

87 + 78 = 165

165 + 561 = 726

726 + 627 = 1353

1353 + 3531 = 4884

그러면 최종적으로 4884 의 팰린드롬 수가 나오게 되었다!

 

 세상의 존재하는 모든 수가 최종적으로 팰린드롬의 수가 될 것인가? 에 대한 이슈가 있다. 그 논란의 중심에 있는 수는 바로 196 이다. 많은 도전가들이 196을 이용해 팰린드롬의 숫자를 만들고자 노력했지만 여전히 미궁에 빠져있다. 정말 팰린드롬의 수를 만족할 것인지의 여부는 196을 팰린드롬의 숫자가 되어야지만 그 사실을 깨달을 수 있다. 또 196이 팰린드롬의 수를 만족하느냐의 여부는 딱히 중요치 않은 사실일 수도 있다. 그러나 알고리즘의 세계는 호기심 많은 프로그래머들의 도전의 장이다.

 

둠즈데이 알고리즘

 자 이제 날짜가 주어지면 요일을 맞춰보는 일을 해보자. 그레고리력에 따르면, 4로 나누어떨어지면서 400으로도 나누어떨어져야 윤년을 만족한다. 이 때, 평년의 경우 2월 28일, 윤년의 경우 2월 29일을 둠즈데이라고 부른다. 그리고 둠즈데이와 같은 요일을 가진 날들을 각각의 달마다 외워두면 요일을 계산하기 쉬워진다. 따라서 매달 둠즈데이는 다음과 같다.

4월 4일	6월 6일	8월 8일	10월 10일	12월 12일
9월 5일	5월 9일	7월 11일	11월 7일	3월 7일

 위 표에 해당되는 날짜들은 둠즈데이(2/28 혹은 2/29)의 요일과 같다. 이 때, 해가 바뀔 때마다 (1년이 지날 때마다) 둠즈데이의 요일이 한 칸씩 달라진다. 윤년의 경우에는 두 칸씩 달라진다. 2003년의 둠즈데이(2월28일)은 금요일이었다. 그렇다면 2004년의 둠즈데이는 토요일이다. 이러한 계산을 빠르게 하기 위해서 콘웨이의 리스트와 같은 암기 리스트도 생겨났다. 6, 11.5, 17, 23, 28, 34, 39.5, 45, 51, 56, 62, 67.5, 73, 79, 84, 90, 95.5 이 리스트의 의미는 19**년도 라고 했을 때 **에 오는 숫자들의 나열이다. 이 리스트에 있는 년도의 둠즈데이는 모두 수요일이다. 이때 11.5의 경우는 1911은 화요일, 1912는 목요일이라는 의미이다. 

 이제 1998.02.04 의 요일은 언제였는지 계산해보자. 콘웨이 리스트에 따르면 1996년도의 둠즈데이는 목요일이므로 1998년도의 둠즈데이는 토요일이다. 2/28(토) 이고 7*4=28 이므로 1월 31일의 요일또한 토요일이다. 2/1(일) 2/2(월) 2/3(화) 2/4(수) 따라서 1998.02.04 는 수요일이다. (안궁금할지 모르지만 진오의 생일이다.)

다음은 미래의 년도에 대해서 요일을 계산할 때 유용한 달력이다.

 

사운덱스 알고리즘

 영어이름을 관리하기 위한 알고리즘으로 2차 세계 대전 때 미국 군인들의 개인 기록을 관리하는 데 사용 되었고, 1880년에서 1930년에 이르기까지 인구 통계 조사에도 사용되었으며 오늘날 여러 가지 소프트웨어의 철자 확인기 엔진 속에도 포함되어 활용되고 있다고 한다. 사운덱스 알고리즘의 원리는 다음과 같다.

 

[단계 1] 이름의 첫 번째 글자를 저장하고, 첫 번째 글자를 제외한 나머지 글자 중에서 a, e, h, i, o, u, w, y를 모두 제거한다. 

[단계 2] 이름 안에 존재하는 글자들에 다음과 같은 번호를 부여한다.

b, f, p, v --- 1

c, g, j, k, q, s, x, z --- 2

d, t --- 3

l --- 4

m, n --- 5

r --- 6

[단계 3] 원래 이름에서 서로 인접하여 연속으로 나타나는 글자는 맨 앞에 하나만 남기고 나머지는 제거한다.

[단계 4] 최종적인 결과를 '글자, 숫자, 숫자, 숫자' 의 형태로 맞추기 위해서 숫자가 세 개 이상이면 나머지는 생략하고, 세 개 미만이면 뒤에 0을 붙여서 형태를 맞춘다.

 

Jinno 라는 이름을 사운덱스 알고리즘에 대한 입력으로 만들어보자. 단계 1에 의해서 jnn만 남는다. 그리고 나머지 과정을 수행하면 최종적으로 J500이 된다.

 

메르센느 소수

수학자 메르센느는 하나의 식으로 모든 소수들을 구하고 싶어했다. 그러나 대부분의 소수가 해당 식을 맞는 듯해보였지만, 이윽고 속속들이 만족하지 않는 소수들이 발견되었다. 계속해서 예외사항이 발생하고 if-else 구문으로 얼룩지자, 사람들은 그것을 버리지 않고 새로운 알고리즘으로 탄생시켰다.

" p가 소수일 때 2^(p-1)이 소수면, 그것은 메르센느 소수라고 한다. "

 

다음 사이트는 최대의 메르센느 소수를 찾기위한 탐험적인 프로그래머들의 웹 페이지이다.

https://www.mersenne.org/

Great Internet Mersenne Prime Search - PrimeNet

 

 

유클리드 알고리즘

 두 자연수 m과 n이 주어졌다고 하자.(m>n) 이 때, m과 n 사이의 최대공약수를 구하는 것이 바로 유클리드 알고리즘이다. 이 알고리즘은 다음과 같다.

[단계 1] m을 n으로 나눈다. 나머지를 r이라고 한다.

[단계 2] 나머지 r이 0이면 n이 최대공약수이다. 나머지가 0이 아니면 m의 값을 n으로 설정하고, n의 값을 r로 설정한 다음 [단계 1]로 되돌아가서 반복한다.

 

582 = 129 * 4 + 66

129 = 66 * 1 + 63

66 = 63 * 1 + 3

63 = 3 * 21 + 0

따라서 582 와 129 사이의 최대공약수는 3이다.