결론1. "안 볼 책은 사지 말자. 못 볼 책도 마찬가지다."

" 사놓고 언제가 본다는 환상은 버리자. 그 돈으로 MG 건프라를 하나 더 사자. " - sigmadream

4년제 대학교의 컴퓨터 공학를 비롯한 유사 학과의 경우 2학년이 되면 대부분 "자료구조와 알고리즘"을 배우게 될 것이다. 1학기에 중간까지 공부하고 끝내는 곳도 있고, 2학기에 걸쳐서 책 전체를 다 공부하는 학교도 있다. 아주 좋은 학교는 2학기 동안 공부하고, 1학기 동안 프로그래밍 학습을 겸하는 곳도 있다. 만약 당신의 학교가 "자료구조와 알고리즘"을 3학기 이상 학습한다면 굉장히 훌륭한 교육환경이라 말할 수 있다. 결론적으로 "자구와 알고"는 학습 시간이 길고, 학습 비용이 높다. 그렇기 때문에 학교에서 제대로 공부해두지 않으면 평생을 걸쳐서 넘어야 할 산이 된다. 대학교 4년을 통털어서 자구, 알고, 컴구, 컴파일러는 취업해서 배울 수 있는 과목이 아니기 때문에 충실하게 학습해야 한다.

본격, 내 맘대로 서평 열전(2015 업데이트)

이렇게 중요한 과목이다 보니 많은 사람들이 "자구와 알고"에 관한 책을 검색하고 구매하기도 한다. 많은 사람들이 자구와 알고의 '타는 목마름'을 해소하기 위해서 신 새벽 뒷골목 어딘가에서 검색에 열중한다. 구글 인터넷에 "자료구조 알고리즘 추천 교재"를 검색하면 많은 책들이 쏟아져 나오는데, 내가 읽고 공부한 책을 중심으로 나열해 보면 다음과 같다.(나열 순서는 주관적인 의미가 담겨있다. 그러니 너무 신경쓰지 말자)

• 윤성우의 열혈 자료구조, 윤성우
• C로 배우는 알고리즘 1,2, 이재규
• [파이썬으로 배우는 실전 알고리즘](파이썬으로 배우는 실전 알고리즘), Massimo Di Pierro
• 다양한 예제로 학습하는 데이터 구조와 알고리즘, Narasimha Karumanchi
• Introduction to Algorithms 3rd, Thomas H. Cormen
• 알고리즘 문제 해결 전략, 구종만
• 문제로 풀어보는 알고리즘, 김용혁, 황인욱
• C로 쓴 자료구조론, HOROWITZ
• Programming Challenges - 알고리즘 트레이닝 북, Steven S. Skiena
• The Art of Computer Programming 3, 2, 1, 4, 도널드 커누스
• 열혈강의 자료구조, 이상진
• 뇌를 자극하는 알고리즘, 박상현
• 알고리즘이 보이는 그림책, ANK Co.,Ltd
• (절판) C로 구현한 알고리즘, Kyle Loudon

(본격 2015년도 업데이트 포함) 저 많은 책 더미에서 뭘 봐야 할까?

• 나는 C로 쓴 자료구조론, HOROWITZ으로 공부했다. 바보 같은 짓이긴 하지만 그 책을 다 외웠다. 왜냐하면, 중등 컴퓨터 교사 임용 시험의 자료구조 과목을 위해선 이석호 교수님이 번역하신 C로 쓴 자료구조론만 외우면 되기 때문이다. 책을 다 외웠음에도 불구하고 코딩 능력이 일취월장 하지 않았다. 왜 그런가 생각해보니 이론만 배웠기 때문이다. 이론만 배워서 입으로 코딩하는 방법을 먼저 배워서 그렇다. 머리속은 슈퍼 개발자 흉내를 내고 있지만 실제 만드는건 '버블 소트' 정도였다. 이 책은 '이론'에 특화된 책이다.

• C로 배우는 알고리즘은 자료구조에 대한 내용보다 알고리즘의 내용이 더 많다. 책도 2권으로 나와있기 때문에 분량도 제법 많다. 무엇보다 이 책은 C언어에 대한 적응력을 굉장히 높여준다. 이 말을 뒤집으면 C에 대한 적응력이 없으면 난이도가 급상승하고 코딩 실력이 뒷받침 되지 않으면 책에 나온 코드의 대부분을 컴파일 할 수 없다. 책에 나온 예제는 'Turbo-C 2.0'을 기준으로 설명하고 있으며, 예제는 3.5인치 디스켓에 담겨있었다. 물론, C에 대한 적응력이 조금이라도 있으면 중급^[1] 정도의 난이도라고 할 수 있지만 쉽지 않은건 마찬가지다. 어렵긴한데, C언어의 고급 기술이나 트릭을 굉장히 많이 배울 수 있다. 이 책은 C에 특화된 책이다.

• 윤성우의 열혈 자료구조는 초보자가 보기엔 최고의 책이다. ADT 설명부터 시작해서 동영상 강의까지 제공하고 하기 있기 때문에 초급자가 보기에 더 없이 좋다. 적당한 수학적 지식, 읽기 쉬운 코드, 알기 쉬운 설명등 초심자가 보기에 더 없이 좋은 책이다. 이 책은 초심자에 특화된 책이다.

• 많은 사람들이 최고의 책으로 찬사를 보내는 Introduction to Algorithms와 The Art of Computer Programming는 코드가 거의 없다. 그래서 금단의 열매다. 이 책을 보고 코드를 작성해서 실제 '실험'을 진행할 수 있는 수준이라면 최고의 책이지만, 중급자 이하의 경우에는 이 책은 독이다. 흔한 말로, '독이든 독배'되겠다. 금단의 열매라고 하기엔 먹으려고 들다가 굶어죽는 경우가 너무 많다. 이 책들은 독이다. 그러나 이겨내면 내성이 생긴다.

• 다양한 예제로 학습하는 데이터 구조와 알고리즘은 C와 Java 두 권으로 출간되었다. 작년에 나온 책이다 보니 내용이 다른책에 비해서 알뜰하다. 책을 절반 정도만 봐도 다른 교재에서 다루는 대부분의 내용은 커버한다. 그리고 책이 C와 Java로 나와있기 때문에 대학생의 경우 C로 된 걸 먼저보고 Java로 된걸로 복습해도 나름대로 의미있겠다. 그런데 요즘은 대학교에서 C를 학습하지 않다고 하니 그럴경우 Java를 보는것도 나쁘지 않다. 이 책은 대학교 1학년에 특화된 책이다.

• 알고리즘 문제 해결 전략은 프로그래밍 대회 문제를 소개하고 해설을 담은 책이다. 책이 2권으로 구성되어 있는데, 1권부터 읽지 말고 2권부터 읽길 권한다. 자료구조가 2권에서 소개되기 때문이다. 문제 중심으로 풀어나가기 때문에 다른 책에 비해서(응?) 이론적인 부분이 많이 생략되어 있다. 반면에 문제 중심으로 이뤄져있기 때문에 자구 및 알고의 적응력을 높일 수 있다. 이 책은 알고를 사용한 코딩에 특화된 책이다.

• 문제로 풀어보는 알고리즘은 분량이 1권으로 구성되어 있어서 좋다. 다른 어떤 점보다 좋은 것은 분량이다. 당연히 책의 분량이 작기 때문에 문제의 양도 많지 않고, 이론적인 소개도 소박하다. 그럼에도 불구하고 이 책을 소개하는 이유는 이 책을 쓴 저자들이 생각보다 많은 '삽질'을 권장하고 있기 때문이다. 만약 적당히 재미있는 문제를 찾고 있다면 해당 교재에서 '3장, 5장, 7장, 8장'을 권한다. 이 책은 삽질을 통한 깨달음을 추구하는 책이다.

• 파이썬으로 배우는 실전 알고리즘은 여러가지 알고리즘으로 구성되어 있다. 그런데 알고리즘 교재의 특성을 전혀 반영하고 있지 않기 때문에, 필요한 부분만 읽기에 좋다. 알고리즘 책은 통상적으로 '탐욕(Greedy), 분할-정복(Divide and Conquer)' 등으로 구성되는데, 이 책은 앞 부분에 정통적인 알고리즘 기법을 소개하고 중반 이후에는 '수치', '확률', '난수' 등에 대해서 다룬다. 이 책은 수학적 표기법을 알고리즘으로 표현하는 방법에 특화된 책이다. 그리고 파이썬으로 알고리즘을 소개하고 있다는 또 다른 장점도 있다. C, Java는 머리에서 지우자

• 열혈강의 자료구조는 선형 자료구조를 자세히 설명하고 있다. 트리, 그래프에 해당하는 부분도 자세히 설명하고 있으나 내가 읽어본 결과 조금 난해한 면이 있어서 추천하지 않는다. 이 책은 선형자료구조가 매우 잘 설명된 책이다.

• 뇌를 자극하는 알고리즘 이 책의 특징은 자료구조와 알고리즘을 모두 다루고 있다. 앞의 4장에선 자구를 다루고, 뒷부분에선 알고리즘을 다룬다. 이 책은 자료구조나 알고리즘을 공부한 학생이나 직장인이 가볍게 복습하기에 좋은 책이다.

• (절판) C로 구현한 알고리즘 이 책은 중급자 이상이 보기에 좋은 책이다. 그런데 아쉽게도 절판이 되어서 구하기 쉽지 않다. 이 책의 경우 코드가 책이 1/3 이상을 차지하고 있고 '집합', '수치(보간법)', '기하'에 관한 내용이 컴파일 가능한 코드로 제공되기 때문에 매우 유용하다. 이 책은 소스코드라도 구해서 읽어보길 권한다.

• 알고리즘이 보이는 그림책 자료구조나 알고리즘 초보자가 많이 본다고 알려졌으나 내가 생각하기에 중급자 이상이 보기에 좋다. 특히 자료구조를 '그림'으로 그리는 방법을 배울 수 있으니 꼭 참고하자. 자료구조 중에서 '선형자료'는 A4에 그림으로 그릴 수만 있으면 코드를 왜우지 않아도 코딩이 가능하니 '자료구조'를 도식화 시키는 방법을 배울 수 있다. 가격도 저렴하니 하나 사두고 따라 그려보면 도움이 많이 된다. 이 책은 자료구조와 알고리즘을 도식화 시키는 방법을 연습하기 좋은 책이다.

"이론보단 실전이 중요하다."

2013년 이후에 발매된 알고리즘 책은 전문적인 깊이를 추구하기 보다는 문제 풀이와 수학공식을 코드로 풀어내는데 집중하는 경향이 있다. 취업이 중요한 시기가 되었기 때문인지, '코딩 인터뷰' 관련 책도 몇권이 출간되었다. 어떤 관점에서 보면 '문제 중심의 알고리즘 교재'는 취업자를 대상으로 한 '요령'만 가르친다는 오해를 불러일이킬 수 있다.

그렇지만 나는 계속해서 '문제 풀이 중심의 알고리즘 교재'가 출간되길 바란다. 이론적인 깊이를 불러오는 교재가 서서히 출판되지 않고 있다는 지적도 있지만, 국내의 교육 현실에서 이론적인 교재보단 코드와 풀이 중심의 교재 중심의 학습이 더 강조되어야 한다. 그리고 이론적인 교재는 TAOCP나 ITA 정도면 충분하다고 판단된다.

문제는 대부분의 학습에서 실습은 뒷전으로 미뤄지고, 중간고사와 기말고사를 중심으로 학습이 진행된다. 시험중심으로 진행되는 학습의 가장 큰 문제는 '밸런스'가 무너진다. 이론과 실습의 비율이 적절하게 배합되지 않으면 '이론은 의미없고, 실습은 부담' 될 뿐이다.

우리가 금단의 열매(혹은 독이든 독배)라 부르는 교재는 모두 '구현'에 대한 내용이 빠져있다. 하물며 TAOCP는 이론도 죄다 수학공식으로 도배를 해 놔서 읽는다고 다 되는 책이 아니다. 심지어 1권에서 소개하는 MIX는 유사 기계어로 진행되기 때문에 약간의 현기증도 동반한다. 무엇보다 TAOCP는 '구현'보다 해당 이론의 증명 과정이 중요하다. 그나마 TAOCP에 비해서 괜찮다고 평가받는 ITA는 알고리즘을 '매우' 잘 설명하고 있지만 구현에 대한 것은 P-Code로 대체되어 있다.

가장 큰 문제는 좋다고 알려진 이론서를 다 읽어본 사람이 극소수란 점이다. 그렇기 때문에 다들 칭찬을 하지만 어디가 좋고, 왜 좋고, 누구에게 도움이 되지는 쉽사리 말하기 힘든면도 존재한다. 앞의 두 권은 국부론이나 자본론처럼 '누구나 알고 있으나 읽진 않은 책'의 대표적인 교재라 할 수 있다.

과도한 이론 중심 학습과 금단의 열매(혹은 독이든 독배)에 대한 무비판적인 칭찬은 소위 말하는 '입프로그래머'를 탄생시킨다. 입으론 천지창조도 하고, UML 다이어그램 따위는 안중에도 없이 모든 코드를 한 번에 '리팩토링' 시킬 수 있는 능력의 소유자 말이다. 내일 당장이라도 운영체제 하나 만들 수 있는, 차세대 '리더들'을 대거 양성시켰다. 내가 알고 있는 것과 구현할 수 있는 것을 분명히 구분 할 수 있어야 함에도 '내가 알고 있으니 구현'도 가능하다고 믿는 특수한 부류의 개발자가 탄생하게 된다. 이론적인게 중요하지만, 실습의 밸런스가 무너지면 허망하다.

"자료구조와 알고리즘"을 처음 접한다면 "이론적"인 교재를 선택하는 것이 옳다. 틀린선택이 아니다. 하지만 무턱대고 '수학'으로 도배한 책을 선택하기 보다는 "구현"에 대한 측면을 고려한 교재도 고민했으면 한다. "구현"만 추구하는 교재도 좋지 않고, "이론"만 늘어놓는 교재도 멀리해야 한다.

그리고 독이든 독배는 사놓고 읽을리 없다. 그러니 일찌감치 포기하자. '난 아닐꺼야!'라고 생각한다면 독이든 독배의 독을 이겨내기 바란다. 건승을 빈다!

그대가 무엇을 선택하든 '코드가 함께 하길(may the Code be with you)'

결론2. "자료구조 교재의 경우 ADT없는 책은 사지마라."

오래전에 나온 자료구조 교재와 지금 판매되는 교재의 가장 큰 차이점이 뭘까? 내용일까? 아니면 분량일까?

놀랍고 신비하게도 교수님들께서 20년전에 참고한 책이나 지금 서점에 파는 책이나 내용은 '똑같다.' 다른 내용이 없다. 근데 유독 한 군데 차이가 나는게 있다. 그것은 "ADT". 지금 판매되는 책의 대부분은 자료구조의 명세라 불리는 ADT가 포함되어있다.

간단하게 자구책에 대해서 소개하면, 자구책의 대략적인 내용은 이러하다.

1장에서 자구에 대해서 설파한다. 고마운 책은 수학적 표기법 일명 O(n)를 1장에 몰아서 가르쳐준다. 현기증을 불러오는 대부분의 책은 2장에서 '잘' 쓰지도 않는 최선, 최악, 평균(오메가, 빅오, 세타)이런거 가르쳐준다. O(n)을 제외하고 평균이 두 군데 정도 쓰이지만 '최선, 최악, 평균'에 관련된 증명도 나오고, 연습문제엔 좀 더 복잡한 점화식도 나온다. 현기증이 난다.

대망의 3장에선 배열을 가르쳐준다. 4장에서 Linked List, 5장은 스택, 6장은 큐(혹은 데크)를 배열과 Linked List를 사용해서 구현하는 걸 가르친다. 특히 5장은 '수식표기법(전위, 후위, 중위)' 이런걸로 연습문제를 풀고, 6장은 데크를 가지고 비행기가 착률을 하니 마니 하면서 현기증 나게 한다.

7장에선 트리, 8장에선 그래프를 배우고 도날드 쿤스 형님이 사랑하는 다이젝스트라의 이론도 배우면서 뭔가 뿌듯할 수 있는 기회를 얻고, 9장은 정렬을 배운다. 뭐니 뭐니해도 정렬의 꽃은 퀵소트와 머지소트 되겠다. 그리고 요상한 정렬도 '많이' 배운다(아주 많이!). 10장은 해쉬, 11장은 트리에 대해서 배운다. 주로 B트리와 그 패밀리를 중점적으로 배우게 된다.

어마어마하게 많은걸 배운다.

"배우긴 뭘 배워.. STL에 다 있고, Collection에 다 있는데 라고" 울부 짖어봐야 소용없다. 앞에서 열거한건 다 할 수 있어야 한다(한땀 한땀, 당신의 보드라운 손으로!) - sigmadream

자구책을 구매할 땐 서점가서 "ADT" 혹은 "추상 자료형" 이런거 있는지 확인하고 사자. 왜냐하면 ITA는 ADT 대신에 P-Code만 있다. TAOCP는 P-Code 조차 없다. 대신에 OP-Code가 있다(참고로 도날드 쿤스 형님은 MIX란걸 만들어서 OP-Code로 알고리즘 설명하신다). 결론적으로 말해서 우리가 못/안 보는 책은 ADT가 없다.

그럼 ADT가 뭘까? ADT는 "추상 자료형"이다. 듣는 즉시 이 단어가 얼마나 '난감한지' 느낌이 온다. "추상"이란 단어 들어가서 쉽게 풀린 예가 없다. 추상 객체, 추상 클래스, 추상화 등등 '추상'이란 접두/접미가 붙는 단어는 뭔가 기분이 좋지 않다(기분탓이다). 거기다가 "자료형" 이란 단어가 결합되면 뭔가 클래스 같기도 하고, 아닌것 같기도 한 느낌이 들었다가 사라진다.

흔히들 ADT는 '자구의 명세'라고 한다. 자료구조가 구현해야 하는 기능에 대한 명세이기 때문에 당연히 구현에 대한 말은 없다. 왜냐하면 ADT는 언어와 '독립적'이기 때문이다. 어느 언어를 사용하던 ADT에 표기된 기능만 작동하면 문제가 없다는 뜻이다. 즉, 조향기로 바퀴를 움직이는 물체를 차로 정의하면 벤츠도 차고, 티코도 차고, 자전거도 차가 된다.

ADT에 대해서 조금 더 첨언하자면, '자료구조를 사용하여 연산할 수 있는 함수 목록'이라 간주해도 된다. 예를 들어서 '은행계좌'라는 자료구조를 사용한 ADT는 '입금, 출금, 대출, 공과급 납부, 신용카드 연동' 등과 같은 연산을 할 수 있는 'deposit, withdraw, loan, utilityBill, checkCard' 등의 함수목록를 지칭한다고 생각해도 무방하다.

레포트, 기말고사, 실습 평가의 경우 아래와 같은 형태의 '함수 원형'만 나오는 경우가 있다. 함수 원형이라도 나오면 다행인데, 약간 난이도가 높은 문제는 해당 문제에서 'ADT'를 설계하고 구현하라고 하는 문제가 출제되기도 한다. 여튼, ADT를 참고하라고 하는 문제를 많이 접하게 된다. 해당 목록이 ADT라고 할 수 있다. 해당 목록을 보고 Linked List 자료구조를 가지고 아래 제시된 연산(혹은 함수)를 구현하면 된다.

int LInsert(int iData, int *pData);
int LDel(int *curPos, int *pData);
int ...

자구의 진정한 가치는 ADT이다. 자구 열심히 배워서 어디에 쓰나면 ADT를 가지고 프로그램 설계 및 구현에 사용한다. ADT를 알아야 배운 자구를 써먹을 수 있다. 아무 곳에나 크루스칼 알고리즘 갈기면 되는게 아니다. 무조건 퀵정렬 한다고 좋은게 아니고, 완전 이진 트리가 좋다라는 건 이론적으로 배우지만 구현에선 배열로 만드나 Linked List로 만드나 상관없다. '완전 이진 트리' ADT만 충족하면 된다. 그리고 ADT만 충족하면 해당 알고리즘과 코드를 조금이라도 재사용할 수 있다. 그리고 회사 업무에선 기본 자료구조가 아니라 '고객', '영업', '판매사' 등과 같은 형태의 굉장히 모호한 주체가 '자료구조'가 되고 해당 자료구조에 대한 연산을 구현하게 된다.

ADT 없는 자료구조 책은 구매할 때 조심하자. 만약 책에 ADT가 없으면 스스로 ADT를 만드는 방법도 좋다.

'ADT가 함께 하길(may the ADT be with you)'