TopCoder 탑코더 알고리즘 트레이닝

smackdown***l2013-12-01

[Topcoder 알고리즘 트레이닝(한빛미디어)] 기존 알고리즘 풀이집이 배려하지 못한 자들을 위한 책

매니아틱한 프로그래밍 경연 사이트에서 집단지성을 활용하는 기업 과제 해결을 하는 성공한 기업에 이르기까지, TopCoder Community (http://community.topcoder.com/tc)를 지탱해 온 핵심은 자동화된 투명한 채점 기준, 랭킹 시스템, 그룹 분배 시스템 등의 노하우가 담긴 온라인 대회 체계와 퀄리티 높은 알고리즘 문제들이었다.

Topcoder 알고리즘 트레이닝은 이러한 퀄리티 높은 알고리즘 문제들을 난이도에 따라 분류하고, 일반적인 알고리즘 이론 중 문제 해결에 유용한 일부를 뽑아내어 문제를 푸는 방식에 녹여내어 설명하였다.

Topcoder는 우리나라에서는 거의 알고리즘 매니아들만 이용하는 사이트이다. 프로그래밍 대회 정보나 알고리즘적인 사고에 대한 중요성이 잘 인식되지 않은데다가, 영어로 된 사이트이고, 가입해야 하는 양식이 꽤나 많은거에, 좀 오래된 웹 디자인과 자바 애플릿을 쓰는 것이 낯설다.

이러한 점을 고려하여 책의 도입부에서는 프로그래밍 대회를 초보자들도 참여할 수 있게 독려하고, Topcoder의 시스템, 가입 방법, SRM이라는 대표 단기 대회에 참여하고 해당 툴 쓰는 법에 덧붙여 기본 프로그래밍 지식을 알려준다.

SRM 시스템에 들어가보면 옛 프로그래밍 툴들의 향수가 나는 디자인이 드러난다. 음성 디자인에 어딘가에 접속하는 듯한 느낌이 드는 첫 화면.

잘 접속한 후에는 수준별 그룹 분배를 하고 경쟁 시간대와 비경쟁 시간대에 따라서 메뉴가 구분된다.

Topcoder는 Division1과 2로 그룹이 나뉘는데, Division 1은 일정한 rank를 넘어야 진입할 수 있는 권한이 부여된다. 각 Division에서는 출제되는 문제가 각각 3개인데, 정확히 초급, 중급, 고급의 난이도 하나씩이다.

이 책에서는 초반 내용으로 Division 2의 초급 난이도 문제들에 대해서 넓은 이해를 하고 들어간다.

시뮬레이션, 전체 탐색, 시간(걸리는 시간)/공간(메모리 할당) 예측 계산 이라는 큰 주제로 엮어간다. 앞의 두가지 주제는 어떤 알고리즘 문제에 대해서도 가장 직관적으로 가져갈 수 있는 툴인 셈이다. 시뮬레이션은 마치 현실에서 똑같은 일을 할 때 행동 하나하나를 코드 한줄한줄로 옮기는 셈이고, 전체 탐색은 효율성을 고려하지 않은 채 전체 데이터를 가공할 수 있는 기본 방법론이다. 시간/공간 예측 계산은 아주 rough한 예측 틀만 제공했지만 문제푸는데는 무방하다.

동시에 이러한 분야에 진입할 때 겪게 되는 몰입 방해 요소들을 하나씩 짚어주면서 알고리즘의 세계에 편안하게 들어올 수 있도록 해준다. 예를 들면, 코딩하는 것 이외에 생각해야 하는 출제자 의도 파악, 상수 범위 제한이나 러닝 타임 제한, 메모리 할당 제한, 그리고 고급 수학들에 대한 두려움을 ‘문제 풀기 전에’ 라는 코너에서 잘 추려내어 설명해준다.

또한, 시각화된 예시들을 통해 문제에 대한 직관적인 이해를 돕고, 문제 해설은 물론, 기존의 알고리즘 풀이집들과는 다르게, 다양한 독자들을 배려해서 모든 문제에 대해 C++, C#, JAVA 풀이를 제공한다. 코드 해설이 끝난 뒷 공간에 작가가 들려주는 간단한 노하우와 이야기는 옆에서 친절한 선생님이 모를 만한 것을 미리 알려주는 듯하다.

중급 카테고리에서는 Division 2의 중급, 고급 문제들을 다룬다. 가장 많은 초보자들이 더이상 나아가는데 힘들어하는 DP(동적 계획법)을 최대한 많은 문제에서 쉽게 서술해내려는 작가의 노력이 많이 들어가 있다. 또한, 탐색 범위 한정 알고리즘이라는 챕터로 탐욕 알고리즘과 탐색법, 해밀턴 패스와 같은 응용 기법들을 하나의 맥락에서 이해하게 해준다.

상급 카테고리에서는 Division 1의 문제들을 다루는데, 이곳의 포인트는 한 문제에 여러가지 접근의 해설을 붙인다는 것. 그동안 초보자들에게 가혹했던 알고리즘 풀이집의 방식을 많이 바꾸어낸 점 중 하나로, 전체를 이미 본 자들만 쓸 수 있는 어려운 이론을 적용할 것이 아니라, 전체의 일부분을 여러 가지 접근 방식(다양한 자료구조, 수학기법, 알고리즘 기법, 심지어 실패한 방법+피드백까지..)으로 들여다봄으로써 자연스럽게 깊은 이해를 이끌어내려는 노력이 엿보인다.

마지막 장은 ‘수학 문제’라는 제목인데, 굉장한 난이도와 추상적인 이해의 한계가 곁들여진 끝판왕의 모습과는 달리 아주 쉬운 중학교 수준의 수학만 언급을 한다. 가장 어려운 이야기가 유클리드 호제법..

그리고 이 장의 문단에서 ‘수학’을 핵심 과목으로 배워온 나 같은 친구들이 ‘프로그래밍’이라는 것에 접근하는 방식을, ‘간파한’ 아주 재미있는 문장이 나온다.

“(수학지식의) 사용 목적은 .. 다르지 않습니다. 많은 사람들이 수학적인 느낌이 강한 (알고리즘 류의) 문제들을 보면 중고등학교에서 배운 수학처럼 O(1)의 수식으로 예쁘게 풀려고 합니다. (중략) “

O(1)의 수식.. 혹시나 이 말이 무슨 말인지 궁금다면, 수학 문제의 주관식 답란 공간에 딱 들어가는 길이의 수식으로 생각하면 된다. 현실의 문제들은 아주 복잡하고 깔끔하지 않고 난잡하고 불확실한 것들이 많음에도, 수학을 중요하게 배우는 우리는 다른 학문에서조차,추상적이고 깔끔하고 핵심이 모인 답을 원하지는 않는가?

이러한 생각에 공감하지만 (생산적으로) 직접 느끼고 싶은 자연계 학생이나, 프로그래밍을 잘하는데 있어 지름길과 재미있는 방법론을 원하는 사람이라면, 꼭 한번 볼만한 책임은 분명하다.