브라이언 크리스천, 톰 그리피스 지음
이한음 옮김
청림 출판
올해 내가 꾸준히 하려고 노력했던 것 중에 알고리즘 공부가 있었다. 일반적으로 알고리즘에 대한 이해 및 문제해결 능력은 개발자의 역량을 측정할 수 있는 좋은 지표가 되고 있다. 요즘 IT기업에서 코딩면접이 일반화 되고 있는 것도 한 예가 될 것이다. 그렇기에 개발자로서 알고리즘 공부를 게을리하고 잘 못한다는 것은 군인이 총을 잘 못쏘는 것과 크게 다르지 않다고 생각한다. 어쨌든 나는 알고리즘을 공부하려고 했지만 결과적으로는 중도에 흐지부지 되버렸다. 내가 이 책을 읽게된 이유는 알고리즘에 조금이라도 정을 붙이고 정말 쓸모있다는 걸 확인하고 스스로 동기부여를 하고 싶었기 때문이다.
책 요약 책은 컴퓨터 과학분야에서 유명한 알고리즘들을 소개하고 실생활에서 실제로 어떻게 쓰이고 있으며, 활용할수 있는지 차근차근 설명하고 있다. 그중 내게 직접적으로 영감을 주었던 주제들만 정리해본다.
최적멈춤책은 "비서문제"를 소개하고 어떻게 37% 법칙이 나오게 되었는지 설명한다. 이 알고리즘은 주어진 시간동안 여러개의 후보를 살펴보고 최적의 선택을 해야할때 적용할수 있다. 확률적 실험을 해본결과 최상의 전략은 총 후보들중 37% 까지 살펴보고 그 이후에 나오는 후보들 중 더 뛰어난 후보가 나타나면 바로 선택하는 것이다. 놀랍게도 이 전략을 통해 최상의 답을 찾을 확률도 37%에 수렴한다. 이것은 보기드문 수학적 대칭성을 지닌 사례라고 한다.
이 37% 법칙은 후보군이 늘어날수록 그 진가를 발휘한다. 100개의 후보중 37%의 확률로 최상의 답을 찾을 수 있듯이 100만개에서도 마찬가지로 확정적으로 37% 법칙을 적용할수 있다는 점이다. 물론 여전히 63%라는 큰 실패확률에도 불구하고 최고의 방어 전략임에 틀림없다. 책은 비서들이 선별 기준이 되는 스펙(학점, 영어점수..)을 가지고 있다고 가정한 변형된 "비서문제" 도 다룬다.
탐색/이용 저녁때 외식을 하기로 했다. 어떤 식당을 갈까? 라는 고민을 하기 마련이다. 이 문제는 컴퓨터과학자가 50여년간 균형을 찾기위해 애써왔던 "탐색/이용 트레이드오프"이다.
우리를 둘러싸고 있는 세계는 익숙하고 검증된 영역이 있는가 하면, 그 너머에는 전혀 경험하지 못한 미지의 영역이 존재한다. 탐색 과 이용의 균형은 이용 가능한 시간과 깊은 연관이 있다고 한다. 내일 지구에 운석이 떨어져 멸망한다는 뉴스를 봤다고 가정했을때 오늘 모임에 나가 새로운 친구를 사귀는 것과 사랑하는 사람과 함께하는 것 중 뭐가 더 가치있다고 느낄까? 가치가 있다는 것은 행복감을 느끼는 정도로 볼 수있겠다. 이럴때 당연하게도 대다수의 사람은 사랑하는 사람과의 시간을 선택할 것이다. 하지만 이용 가능한 시간이 충분할때 다음과 같은 확률이 존재한다고 한다. 주목할 점은 승/패가 0/0일때 즉, 새로운 것에 대한 기대값이 90프로에 육박한다. 과학적으로 새로운 것을 탐구하는 것이 얼마나 현명한 선택인지를 입증한 셈이다.
정렬 컴퓨터과학에서 정렬(Sorting)은 데이터를 특정 기준에 의해서 다시 배열하는 것이다. 일상생활에서 책장에 책을 순서대로 꽂는 일도 정렬이다.
미국에서 1880년대에 인구조사에서 자료를 정리하는 데 막대한 시간과 비용이 발생했다. 이 문제해결에 지대한 공을 세운 인물인 허만 홀러리스는 카드에 구멍을 뚫어 자료를 분류하는 기계를 만들었다. 이를 계기로 그가 세운 회사는 1900년대 초 우리가 익히 알고있는 IBM(International Business Machine) 이라는 회사가 되었다.
컴퓨터 과학의 발전에서 정렬은 큰 의미를 갖는다. 1960년대의 한 연구에 의하면 컴퓨터 자원의 무려 1/4이 정렬문제 해결에 사용되었다고 한다.
정렬과 같은 알고리즘의 성능을 이야기할때 빠질 수 없는 개념이 빅오(Big-O)이다. 정확한 예측이 아닌 문제의 크기에 비례한 작업 시간에 관계에만 관심을 둔다. O(1) 상수시간, O(N) 선형시간, O(N^2) 2차시간 순으로 느려진다.
존 폰 노이만이 1940년대에 최초로 도입한 합병 정렬은 컴퓨터 과학 분야에서 전설로 기록된다. 이 정렬의 성능은 O(N*logN)으로 선형로그 시간이다.