본문으로 바로가기
반응형



Computer Science, Computer Engineering을 전공하는 학생들에게선 뗄래야 뗄 수 없는 존재, 바로 알고리즘 입니다.

요즘은 카카오, 네이버, 삼성전자 등 각종 IT 관련 대기업에서 입사 전형의 일종으로 코딩테스트를 더욱 활발히 진행하고 있고, 그에 따라서 각종 Online Judge 사이트에도 코드 제출량이 급증하고 있다고 하는 데요.


사실 전공 과목으로 알고리즘과 자료구조를 비롯해 각종 관련 과목들을 수강하게 되지만, 이를 각종 알고리즘 대회에서 바로 적용하고 활용하기란 여간 어려운게 아닙니다. 하물며 비전공 학생들이라면, 그 진입 장벽이 더욱 높게 느껴질텐데요.


지속적으로 양질의 IT 서적을 내놓고 있는 도서출판 인사이트에서 알고리즘 대회를 입문하고자 하는 학생들에게 많은 도움을 줄 책을 새롭게 내놓았습니다. 바로 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드> 입니다.



사실 인사이트에서 기존에 출판했던 관련 도서들도 하나같이 도움이 많이 되기로 유명한 책들입니다.

특히 <프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 1/2>는 저자 구종만님의 이름을 따서 일명 '종만북'이라는 애칭으로 불릴 정도로 PS(Problem Solving)과 알고리즘 학습자들 사이에서 유명한 책입니다.


저 역시 시간이 날 때마다 열심히 해당 책을 보고 있지만, 아직 1권 조차 다 보지 못 하였습니다. 사실 <프로그래밍 대회에서 배우는 알고리즘 문제해결 전략> 시리즈는 난이도가 상당하고, 그 분량 또한 도합 1,000페이지를 넘기는 방대한 양이기에, 이번에 새로 출간된 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>를 통해 큰 흐름을 이해하고 넘어가는게 어떤가 생각이 듭니다.



지금 책상 옆에 놓여진 책들을 통해 두께를 비교해보았습니다.

아마존에서 가장 많이 팔리는 프로그래밍 면접 책이라는 카피 문구가 인상적인 게일 라크만 맥도웰 님의 <코딩 인터뷰 완전 분석> 역시 900페이지에 달하는 분량으로, 만만치 않은 양인데요.


아래 두 종류의 도서에 비하면 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>는 상대적으로 굉장히 사이즈가 작아보입니다. 실제로 300페이지 분량으로, 필수적인 내용만 넣고 군더더기는 싹 빼어 학습 분량의 부담을 덜어준 책이라는 생각 마저 드네요.



다시 한번 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>의 표지를 살펴보도록 하겠습니다. 

전작인 <알고리즘 트레이닝 : 자료구조, 알고리즘 문제 해결 핵심 노하우>가 그래프 자료구조를 시각화한 표지 디자인이었다면, 이번엔 트리 자료구조를 시각화한 표지 디자인입니다.


개인적으로 매우 깊은 인상을 받은 디자인이었습니다. 총 15장으로 구성된 전체 내용은 마치 트리구조가 책 속에 구현된 것 처럼, 매우 짜임새있게 구성되어 있습니다. 보통 알고리즘 관련 서적들은 워낙 분량이 방대하여 처음부터 끝까지 통독하는 방법 보단, 필요한 부분을 그때그때 찾아서 보거나 천천히 전체적인 흐름을 학습하는 방법이 많이 선호 되곤 하는 데요.

반면에 짜임새 있게 잘 설계된 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>는 장기간의 학습 계획을 잡을 필요 없이, 단기간에 프로그래밍 대회에서 필요한 지식들과 그 전체적인 흐름을 이해할 수 있도록 도와줍니다.


특히 저자는 안티 라크소넨(Antti Laaksonen) 님으로, 핀란드의 헬싱키 대학교와 알토 대학교에서 교원 겸 연구자로 근무한 분입니다. 우수한 교육 시스템으로도 유명한 핀란드는 그 명성과 함께 IT 교육 역시 굉장히 활성화된 국가 중 하나인데요. 

저자는 2009년부터 2016년까지 국제 정보 올림피아드 등 다양한 국제 프로그래밍 대회에 참가한 핀란드 팀을 지도하고 이끌었으며 이를 통해 프로그래밍과 알고리즘 지도 경험 또한 쌓을 수 있었다고 합니다. 사실 우수한 연구자가 반드시 우수한 교육자라는 보장은 없는데요. 저자의 이러한 경험과 경력은 이미 저자가 우수한 교육자임을 드러내어주며, 학습자들을 쉽고 빠르게 트레이닝 시켜줄 수 있을 것이란 기대까지 하게 해주는 것 같습니다.


저자의 개인 페이지는 [링크] 에서, 본 도서의 원서인 <Guide to Competitive Programming>에 관한 정보는 [링크] 에서 얻으실 수 있습니다.


그럼 이제, 목차를 통해서 구체적으로 살펴보도록 하겠습니다.



제 1장, 경진 프로그래밍에 대한 간략한 설명과 더불어 각종 오프라인 프로그래밍 대회, 온라인 프로그래밍 대회를 설명해주고 있습니다.

또한 CSES(Code Submission Evaluation System)을 이용해 매우 단순한 알고리즘 하나를 풀어보도록 하는데요. 간단한 C++ 코드를 사용하는 해당 예제는 온라인 알고리즘 저지 사이트 등에서 문제를 풀어본 경험이 없는 독자가 기본적인 배경 지식을 하나 만들고 갈 수 있는 부분인 것 같습니다.

사실 상당수 학습자에겐 이러한 단계가 필요치 않겠지만, 오히려 이런 친절한 부분이 책의 타겟 독자층 자체가 굉장히 폭넓다는 것을 말해주고 있습니다


제 2장은 이 책의 주요 예제에서 사용하고 있는 언어인 C++의 언어적 특징, 재귀적 알고리즘과 비트 연산에 대해 알아보고 있습니다.



C++의 기본적 입출력, 수 처리에 관한 방법과 비트연산 등 기본적인 기법을 설명하고 있습니다. 사실 기본적인 내용일수록 정말 꼼꼼하게 공부하지 않으면, 이후 반복 숙달되는 과정에서 빼먹은 부분은 계속 모르는 상태가 되어 나중에 이를 다시 바로잡기 어렵게 될 수 있는데요.

저 역시 2장을 읽으면서 기초적인 내용이라 생각하고 머릿속에 담아놓지 못한 부분들이 종종 눈에 띄었습니다. 따라서 1장 ~ 5장까지는 정말 꼼꼼히 읽어나가는 것이 좋지 않을까 싶습니다.




3장에서는 시간 복잡도(Time Complexity)를 기반으로 알고리즘 효율성의 정의에 대해 알아봅니다. 과거에 알고리즘의 기초적 내용을 공부할 때의 기억을 되살리면, Big-O 표기법의 의미와 O(n), O(log n), O(n^2), O(n!) 등 여러 시간 복잡도를 알게 되었지만, 정작 이게 실제 코드에서 어떤 식으로 적용 되는지는 꽤 나중에 알게 된 적이 있습니다.


본 책에서는 for문 예제를 통해 쉽고 빠르게 시간 복잡도에 대해 이해시켜주고 있습니다. 또한 프로그래밍 대회에서 알고 있어야 할, 문제의 시간제한을 엄수하기 위한 근사적인 효율성 추정 방법에 대해서도 서술하고 있습니다.


마지막으로 실제 예제문제인 최대 부분 배열 합 구하기, 체스판 위에 두 개의 퀸을 서로 공격할 수 없는 위치에 배치시키는 문제를 통해 코드의 효율을 높이는 방법에 대해 알아봅니다. 아직까지 도입부에 가까운 부분이지만, 사실 다른 매체로 여기까지의 내용을 공부하려면 상당한 시간이 걸릴 수 있습니다. 순식간에 읽어나갈 수 있는 분량임에도 핵심은 쏙쏙 담겨 있다는 점이 인상적이네요.



이제 4장에서는 본격적으로 알고리즘 이론에 대해 알아봅니다.

먼저 정렬과 탐색입니다. 본격적인 알고리즘 트레이닝의 첫 발을 내딛는 장이라고 할 수 있는데요. 4장의 서두에서 버블 정렬을 시작으로 간단한 알고리즘에 대해 알아보고, 실제 상황에서 C++을 통해 정렬과 탐색 문제를 푸는 법을 공부합니다. 이론과 실전, 꽤 적절히 배합된 황금 비율을 느낄 수 있는 장이었습니다.


5장은 자료구조를 다루는 장이지만, 자료구조 전체를 다루거나 소개하는 장이라기 보단, C++ 표준 라이브러리에 속한 자료구조 중 몇 가지를 살펴봅니다. 동적 배열, 우선순위 큐 등, C++을 깊게 공부하지 않은 저에겐 문제를 풀때 어떤 것을 활용해야 할지 알게 해주어 많은 도움이 된 부분입니다.



6장은 Dynamic Programming이라는 이름으로 불리는 동적 계획법을 다루고 있습니다.

동적 계획법은 코딩테스트, 알고리즘 대회 등에서 중요한 부분 중 하나인데요. 개인적으로 학습에 골치를 썩던 부분이라 걱정이 되었는데, 분량부터 굉장히 부담이 없었습니다. 약 16페이지 남짓한 부분인데요. 역시 예를 들어 설명하는게 누군가를 이해시키기 제일 좋은 방법인 것처럼, 기본 개념과 메모이제이션, 이후 최장 증가 부분 수열과 짐 싸기 문제 등 모든 부분에서 예제를 활용해 동적 계획법을 적용시키는 방법에 대해 다루고 있습니다. 


사실 책의 중반부에 접어드는 6장, 동적 계획법 부터는 학습에 큰 난항이 있지 않을까 고민도 많이 했습니다만, 조금씩 어렵게 느껴지는 부분이 등장 할 때마다 어김없이 예제과 함께 따라주니 훨씬 편안하게 학습이 가능했습니다.



7장에선 최소 신장 트리, 최단 경로를 구하는 알고리즘 등과 함께 기본적인 그래프 알고리즘에 대해 알아봅니다.

기본적인 용어 정리를 시작으로 인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix), 간선 리스트(Edge List)와 같은 그래프의 표현 방법, 그래프 알고리즘의 핵심인 깊이 우선 탐색(DFS = Depth-First Search), 너비 우선 탐색(BFS = Breadth-First Search)가 서술되어 있는데, 설명이 무척 깔끔합니다. DFS, BFS를 설명할 때에도 많은 군더더기 없이 깔끔하게 처리 과정 일러스트 각각 한 장과 예시 코드 하나로 설명한 점이 눈에 띕니다. 


이후 최단 경로 문제 풀이를 위한 벨만-포드 알고리즘(Bellman-Ford Algorithm), 다익스트라 알고리즘(Dijkstra's Algorithm), 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 등을 공부하게 되는데요. 사실 이러한 알고리즘을 실제로 구현해보고 실전에 써먹어보려면 더 많은 공부가 필요할 것 같지만, 기본 개념을 알고 공부하는 것과 모르고 공부하는 것은 분명 많은 차이를 보이겠지요.

뒤로 가면 갈수록 어려운 부분이 많이 등장하고 있습니다. 


"몇몇 알고리즘 설계 기법은 온라인 게시판이나 블로그 글에만 간단히 소개되는 등 제대로 정리된 자료가 부족하며 상위권 경진 프로그래머들 사이에서만 주로 공유되는데, 이 책은 그런 '민간전승' 기법들을 다루고 있는 점도 눈에 띈다. 활용하기 좋은 프로그래밍 기법, 최신 트렌드 및 대회에서 유용한 트릭까지, 다루는 주제의 폭이 넓고 그 난이도도 다양해서 초보자와 경험자 모두에게 적합한 책이다"


책 표지 뒷면에서 볼 수 있는 문구가 확실히 공감 되기도 하는 데요. 국내 온라인 알고리즘 저지 사이트 중 가장 유명한 '백준 온라인 저지' 운영자이신 최백준 님 역시 소갯말에서 "책의 후반부에는 책으로 만나보기 어려웠던 주제를 소개하고 있어서 좀 더 어려운 문제를 해결하고 싶은 분들께 큰 도움이 될 것입니다." 라고 말하고 있습니다.

앞으로 8장부터 시작해 15장 까지, 남은 8개의 장에서는 고급 기법을 학습하게 되는데요. 확실히 앞서 보았던 것들과는 다른 내용을 보여줍니다.



백준 온라인 저지에서 해밍거리 구하기(Hamming Distance) 구하기 문제를 얼핏 봤던 기억이 나는데요. 8장에선 비트 병렬 알고리즘의 해밍거리 구하기를 시작으로 각종 고급 알고리즘 설계기법에 대해 공부하게 됩니다.

특히 분할 상환 분석의 두 포인터 기법은 과거 C언어 교재에서 봤던 내용이었는데, 직관적인 설명 덕분에 이해가 훨씬 수월했습니다. 


다음 9장은 구간 질의(Range Query)에 관한 것으로, 누적 합 배열(Prefix Sum Array)를 이용한 합 질의에 대한 내용으로 시작합니다.

배열의 부분합이 필요할 때, 매번 필요한 시점마다 부분합을 구하게 되면 O(N)의 시간 복잡도를 가지게 되지만, 만약 누적 합 배열을 미리 구해놓는 전처리 과정을 거치게 되면 이후로는 부분합을 구하는 과정이 O(1)의 시간 복잡도를 가지게 됩니다.

이어서 최소 질의(Range Minimum query)를 위한 희소 테이블 알고리즘(Sparse Table Algorithm), 트리형 자료구조에서 이진 인덱스 트리(Binary Indexed Tree)와 펜윅 트리(Fenwick Tree), 구간 트리(Segment Tree) 등을 살펴보게 됩니다.


9장에 이어서 10장은 트리 알고리즘에 대해 더욱 자세히 알아봅니다.

트리에 대한 기본 개념 및 알고리즘, 트리에 대한 질의 처리, 트리 처리에 대한 고급 기술에 관한 내용인데요. 트리의 기본 개념과 트리 순환, 지름 계산, 최장 경로 등에 관한 내용을 다루고 있고, 전체적으로 그 내용이 무척 다양합니다. 만만하게 생각하고 10장을 읽다가, 다 읽는데만 해도 상당한 시간이 걸렸는데요. 해당 부분을 막힘 없이 읽기 위해선 미리 트리에 대한 내용을 타 매체로 공부하고 진입하는 것이 좋을 것 같습니다.



프로그래밍 대회에서 빠질 수 없는 것이 수학입니다. 심화된 알고리즘 기법으로 가면 갈수록 수학이 뒷받침 되어야만 막힘없이 활용하는 것이 가능한데요. 11장에서는 '수학'이라는 이름 그대로 프로그래밍 대회에서 쓰이는 수학 관련 내용을 정리하고 있습니다.


이산수학을 공부하신 분들이라면 알고 있는 내용이나 익숙한 주제가 많이 등장 하겠지만, 그렇지 않은 부분도 분명히 많을 것입니다. 폭넓은 주제의 수학적 내용이 등장하지만, 하나하나 적절한 분량으로 잘 나눠져있는 덕분에 읽다보면 마치 주제를 하나씩 격파해가는 느낌이 듭니다.

특히 무작위 알고리즘(Randomized Algorithm)의 몬테카를로 알고리즘(Monte Carlo Algorithm)과 라스베이거스 알고리즘(Las Vegas Algorithm), 게임 이론의 님 이론(Nim Theory) 부분은 흥미롭게 읽을 수 있었습니다. 


드디어 마지막 후반부인 12~15장, 고급 그래프 알고리즘부터 고난도 주제에 해당하는 장입니다.

12장에선 기존에 학습한 그래프 알고리즘에서 더 나아가, 더욱 난이도 높은 그래프 알고리즘을 학습하게 되며, 13장에선 기하에 관련된 고난도 문제에 적용할 수 있는 관련 기법과 알고리즘을 살펴봅니다. 특히 다각형 내/외부에 위치한 점의 위치를 판별하는 방법이나 다각형의 넓이를 구하는 방법 등, 단지 수학적 센스만으로는 빠르게 풀기에 난감한 문제의 해법을 알 수 있는 부분이었습니다. 


14장은 문자열 처리를 위한 알고리즘을 살펴보는 부분으로, 문자열 집합을 관리하는 트라이 트리, 문자열 해싱 기법, 접미사 배열 등의 기법을 알아보게 되는데요. 문자열 처리에 관한 주제로 이렇게나 어렵고 다양한 내용이 나올줄은 몰라서, 읽는데에 많은 고생을 했습니다. 온전히 제것으로 만들기 위해선 후반부는 앞으로 여러번 읽어나갈 필요가 있을 것 같습니다.


마지막 15장의 고난도 주제 파트는 고급 알고리즘과 자료구조를 다루는 곳이지만, 사실 지레 겁먹을 필요는 없을 것 같습니다. 대회에 출제되는 고난이도 문제를 풀기 위한 내용이지만, 결국 문제를 해결하기 위한 해법이라는 점은 동일하니까요. 동적 계획법 최적화 부분을 비롯해 15장의 전체 내용을 열심히 읽어보았지만, 실제로 15장의 내용이 저에게 필요해지려면 아직 많은 수련이 필요할 것 같습니다. 



이렇게 책의 전체 내용을 살펴 보았는데요. 책의 부제가 '프로그래밍 대회 입문 가이드'이고, 원제 역시 'Guide to competitive programming'이지만, 사실 경진 프로그래밍 대회를 위해서만 쓰일 책이 아니라는 생각이 듭니다. 

매번 전공 과목을 공부하고, 알고리즘 & 자료구조 책을 학습 하면서도 이 내용들을 실제로 PS에 적용하기에 어려움을 많이 느꼈었는데요. 백준 온라인 저지나 탑코더와 같은 각종 온라인 저지, 온라인 경진대회 사이트를 통해 문제를 바로 풀어보는 것도 좋지만, 일단 전체적인 흐름을 확실히 짚고 넘어가는게 중요하다고 생각되었습니다.


실제로 PS를 하면서 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>에서 읽었던 개념이 나오거나, 전공서를 보면서도 해당 책에서 보았던 내용들이 나오곤 했는데요. 비교적 짧은 기간 동안 읽었지만, 머릿속에 남는 유익한 내용이 굉장히 많았다는 생각도 드네요.


개인적으로 책을 조심히 보는 편이라, 가지고 있는 책 중 낡거나 더러워진 책은 보통 오랫동안 지속적으로 가지고 다니면서 자주 본 책인데요. <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드> 역시 저의 낡고 더러워진 책 컬렉션에 조만간 들어가게 될 것 같습니다. 책이 낡고 더러워지는 만큼 제 PS 실력도 쑥쑥 커 갔으면 좋겠다는 바램이 드네요.


<알고리즘 문제 해결 전략>, <코딩 인터뷰 완전 분석> 등 지금 가지고 있는 관련 책들도 언제 다 읽나 싶지만, 책의 진도가 나갈 때마다 제 실력도 차근차근 성장하고 있음을 느낍니다. 탄탄한 기초 다지기와 전반적인 흐름 정리가 필요했던 저에게 많은 도움을 준 <알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드>, 리뷰어의 기회를 주신 도서출판 인사이트 편집부 관계자 분들께 다시 한번 감사를 전합니다.


읽어주셔서 감사합니다 :)


해당 리뷰는 도서출판 인사이트(Insight)의 리뷰어로 선정되어, 무료로 도서를 증정받고 작성한 것임을 밝힙니다.

반응형