PS/CP 책 리뷰 모음
author: wbjeon2k
안녕하세요, 두 번째 글로 돌아오게 되었습니다.
추석 연휴 동안 누워있는것 보다 조금 더 생산적인 일을 하고 싶은데, 문제를 풀기는 싫어서 글을 쓰게 되었습니다.
제가 현재 보유하고 있는 PS 책 위주로 리뷰를 적어보았습니다.
각 책의 특징, 장단점, 특별한 주제들이나 읽는 순서 등을 소개 하도록 하겠습니다.
2017년 이후 자료들로만 구성 되어 있습니다.
제가 BOJ ID를 17년도에 처음 만들며 입문했을 당시에 구했던 자료들 위주입니다.
다행(?) 스럽게 이후에 PS 책들이 거의 안나와서 outdated 되지는 않았습니다.
함정 책들도 소개 하였으니, 참고하여 꼭 거르시길 바랍니다.
2010년도 초반의 고전 자료들은 제가 PS 입문하기 전이라 없습니다. 제보 바랍니다!
서두 : 왜 굳이 책인가요?
책 리뷰 본문이 궁금하시면 서두는 skip 하여도 좋습니다.
인쇄된 책의 가치
요즘은 PS 정보를 kks227 blog 등 웹에서 얻는것이 대세인데,
그럼에도 불구하고 인쇄 된 책이 가지는 가치에 대해서 의문을 가지는 분들이 계시리라 생각합니다.
인쇄된 책은 (거의 대부분) 유료 입니다.
웹에 무료 정보가 많이 보급 될수록, 역설적으로 좋은 책의 가치는 올라갑니다.
무료 정보가 널리 보급된 요즘 시대에, 유료로 돈을 주고도 얻을 가치가 있는 정보 이기 때문입니다.
조각별로 흩어진 정보를 검증된 전문가가 검수/정리 하는데 필요한 수고비 라고도 생각할 수 있습니다.
아래에 소개 드리는 책들은 상당한 PS 경력을 가진 전문가들이 작성한 책입니다.
장점은 명확합니다. 잘 검증된 내용들 위주로, 클래식한 주제들을 위주로 정리 되어있습니다.
단점으로는, 최신 주제들을 많이 다루지는 않습니다.
다만, 아래 책들에서 다루어 지지 않는 최신 주제들은 CF 레드 이상이 아니면 몰라서 문제가 생기는 일이 딱히 없습니다.
개인적인 배경
알고리즘 책들을 수집하게된 계기는 2017년 2학기 데이터 구조 수업 때문이었습니다.
스택을 이용한 수식 파싱, 다익스트라 알고리즘 등 을 구현 했던 기억이 납니다.
수업에서는 자료구조에 대한 소개만 하고, 응용 측면은 완전히 따로 공부를 해야 했습니다.
그러던 도중에 BOJ에 비슷한 문제들이 많다는 것을 알게 되어서 PS에 관심을 가지게 되었습니다.
지금이야 회사마다 코테가 당연하게 있고, 코테 준비 수단으로 PS가 엄청난 인기를 얻고 있지만,
2017년 당시에만 해도 PS 는 지금처럼 대중화가 되지는 않았습니다.
여전히 정보올림피아드를 즐기는 사람들 외에는 수요가 많이 없었습니다.
따라서, 당시에는 PS 웹 자료가 많이 없었고, 교보문고의 충실한 회원인 저는 당시 시중의 PS 책들을 모두 샀습니다.
데이터 구조 수업만을 위해서는 과한 투자였지만, 지금까지도 공부하며 읽고 있기에 가성비는 최고라고 생각합니다.
저의 내돈내산 책 리뷰가 도움이 되었으면 좋겠습니다.
알고리즘 문제해결 전략 (a.k.a 종만북)
추천 정도: ★★★★★
저자: 구종만, ACM-ICPC 월파 진출자
대한민국 PS 역사에 남을 명작입니다.
이 이상의 수식어는 필요 없으며, 반론의 여지는 없다고 생각합니다.
장점
PS 거의 모든 분야의 표준적인 내용을 담고 있습니다.
방대한 내용을 다루면서도, 굉장히 자세한 설명과 함께 세부적인 내용들을 빼먹지 않습니다.
하지만 방대한 내용만이 이 책의 장점은 아닙니다.
PS 의 본질은 문제 해결 이고, 알고리즘의 적용이 아니라는 것을 알려주는 책 입니다.
해당 알고리즘 공부를 따로 하고, 연습문제의 모델링 phase를 볼 때 이 책의 진가가 나옵니다.
종만북의 최대 장점이며, 종만북을 여러번 읽어도 새롭다고 느껴지는 장점이라고 생각합니다.
‘아는 만큼 보인다’ 라는 말이 있는데, 이 책을 두고 하는 말이라고 생각합니다.
보너스 장점으로, 깔끔한 예제 코드가 제공됩니다.
보통 PS 코딩은 깔끔한 기업 코딩과 달라서 읽기가 힘든 측면이 있는데,
종만북의 예제 코드들은 상당히 깔끔합니다.
특히 DP 파트 int& ret = cache[idx]; 와 같은 우아한 코딩 스타일은 배우지 않으면 익히기 힘듭니다.
단점
챕터 순서대로 읽으면 굉장히 비 효율적인 책입니다!
완전탐색 - DP 초반 - 그래프(스패닝 트리 전까지) 순으로 쉬운 주제들을 먼저 읽고,
나머지 중급 이상의 주제들을 하나씩 즐기는게 좋다고 생각합니다.
처음부터 순진하게 읽으면 1권 중후반 부터 아래 순서대로 최악의 PS 입문을 하게 됩니다.
DP 응용 - 그리디 - 조합탐색 - parametric search - 수치해석/정수론/계산 기하
초급반 주제로 다룰만한 내용이 없습니다.
이렇게 챕터 순서대로 읽는 피해자(?) 들이 속출하여 난이도가 어려운 책이라고 알려져 있습니다.
종만북보다 쉬운 책은 없다고 생각하기에, 적절한 순서대로만 읽는다면 문제 없을것 같습니다.
Special Topics
이 책은 없는 주제를 얘기하는게 더 좋을것 같습니다.
Backtracking (eg. N queen 문제) 를 다루지 않습니다. 참고 바랍니다.
알고리즘 트레이닝 : 자료 구조, 알고리즘 문제 해결 핵심 노하우 (a.k.a 파란책)
추천 정도: ★★★★★ 저자: 스티븐 할림, ACM-ICPC 월파 진출 및 코칭
종만북 보다 더 많은 주제를 실전 압축하여 다루는 책 입니다.
장점
매우 방대한 내용들을 상당히 압축적으로 다루는 책입니다.
ACM-ICPC 팀 노트에 적어둘 것을 염두한 예제 코드 들이라서 매우 알찹니다.
직접 코딩을 하기 귀찮은 주제들을 이 책에서 찾아서 라이브러리 형태로 만들어 놓으면 편합니다.
대회 실전용 책으로서 매우 밀도가 높게 구성 되어있습니다.
단점
입문자를 위한 책이 아닙니다. 절대 아닙니다!
기초 알고리즘들에 대한 설명을 읽기 위한 책이 절대 아닙니다.
비중 있게 다루는 주제들에 대한 설명은 읽을만 한데, 초급 알고리즘은 그냥 설명이 없습니다.
책에 있는 연습문제를 풀기가 굉장히 불편합니다.
UVaOJ 를 사용하는데, 굉장히 오래된 OJ 라서 쓰기 매우 불편합니다.
한 번 시도 해봤는데, 정말 불편해서 다시는 쓰고싶지 않았습니다.
Special Topics
9장 “희귀한 주제” 들에 정말 (역하기로) 유명한 주제들이 대거 분포하고 있습니다.
스티븐 할림이 이 책을 쓸 때만 해도 희귀한 주제였지만, 더 이상 희귀해지지 않은 주제들도 많습니다.
아래 주제들을 포함하여 총 36가지 케이스가 정리 되어 있습니다.
중국인 우편배달부 문제, 디닉, 홉프크로프트-카프, MCMF(홉프크로프트-카프와 따로 다룹니다.), 폴라드 로 소인수분해 ...
알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 (a.k.a 초록책)
추천 정도: ★★☆☆☆
무료로 공개된 CSES CP Book 의 한국 번역 정발본 입니다.
왠지 모르겠지만 두 번째로 소개해드린 파란 책이랑 “알고리즘 트레이닝” 이란 주 제목을 공유합니다.
원하는 책이 있다면 부제까지 잘 살펴보고 사야합니다.
장점
PS 분야에서 인쇄된 책으로 나온 것들 중에서 가장 최신에 출판된 책입니다.
따라서, 최신 주제들을 많이 다루고 있습니다.
통상적인 책들에서 다루지 않고 고수들의 블로그 등으로 알음알음 전승(?) 되던 테크닉을 많이 담고 있습니다.
문제들과 알고리즘의 연결성이 가장 높습니다.
사실상 특정 유형의 문제를 먼저 소개하고, 필요한 알고리즘을 따라 소개하는 형식입니다.
원래 무료 책이라서, 그냥 위 CSES CP Book 링크에서 pdf 받아서 읽을 수 있습니다.
반드시 한국어 자료가 필요한게 아니라면, 무료 원본을 받아 읽는걸 추천합니다.
단점
역시나 입문자용 책은 절대 아닙니다.
어느 정도 실력자들을 염두로 쓴 책이라, 코드 예시가 다른 책들에 비해 매우 적습니다.
문제는, 여기서 나오는 “고급” 주제들을 다룰 정도의 사람들 에게 책의 가성비가 너무 낮습니다.
이 책의 타겟 독자층들은 단원별로 얻어갈 내용이 1개가 있을까 말까 한 수준이며,
타겟 독자층 보다 수준이 낮은 사람들은 새롭게 얻어 갈 내용이 없습니다…
Special Topics
사실상 아래 토픽들 읽어볼게 아니면 이 책을 읽을 이유가 없다고 생각합니다.
그리고 아래 토픽들을 읽는 사람들 이라면 이 책의 나머지 내용을 99% 이상 마스터 했을겁니다.
원래 무료 책인데 그냥 pdf로 읽으세요… 토픽들은 화려합니다.
Burnside Lemma
Sprague Grundy Theorem
Z algorithm
Mo's algorithm
Lazy Propagation(Segtree)
DP Convex Hull Trick
DP DnC Optimization
DP Knuth X Optimization
Meet-in-the-middle
프로그래밍 콘테스트 챌린징 (a.k.a 노란책)
추천 정도: ★★★★
저자: Masatoshi Kitagawa 등 월파 진출자
TMI: Masatoshi Kitagawa(kita_masa) 는 키타마사법 이라는 유명 테크닉의 창시자 입니다.
저자 이름에서 알 수 있듯 일본 책이 원본입니다.
요즘은 절판 되었다고 합니다… 알라딘 같은데서 보이면 바로 사세요.
별점 4점짜리 책 임에도 순위가 밀린것이 절판 때문입니다.
제가 17년도에 살 때만 해도 인기 있는 책이었는데, 왜 절판 되었을까요… 슬픕니다.
장점
지금까지 소개 드린 책들 중에서 문제와의 응용 연결성이 가장 높습니다.
그렇다고 알고리즘만 달랑 적용하는게 아니라 추가적인 디테일이 가볍지만 확실하게 들어 있습니다.
지금까지 소개 드린 책들 중에서 가장 독자층의 범위가 넓은 책이라고 생각합니다.
고급 주제들이 잘 소개 되어 있지만, 그렇다고 초급 주제들이 대충 소개 되어 있지 않습니다.
그럼에도 불구하고 450여 페이지 내에 간결하게 실전 압축 되어 있습니다.
적당한 입문 자료와 함께 읽으면 최고인데, 이제는 구하기가 어려워져서 점점 잊혀가는게 아쉽습니다.
단점
절판이 제일 큽니다… 구하는게 문제입니다.
2011년도에 출판된 책이라서, 이 책에만 다룬 희귀한 내용은 없습니다.
Special Topics
책의 목차 링크로 대신합니다.
현재 기준으로 그렇게 특별한건 없습니다. Kyobo Link
Topcoder 알고리즘 트레이닝 (a.k.a 빨간책)
추천 정도: ★★★ 놀랍게도 2021-09-19 기준, 아직 절판이 안된 책 입니다. (왜?)
장점
문제풀이 입문을 하기에 정말 친절한 책 입니다.
프로그래밍 자체에 입문을 처음 하는 사람도 읽을 수 있는 책입니다. (if else도 가르쳐 줍니다.)
굉장히 기초적인 내용들을 다루며, 프로그래밍 자체에 익숙해질 수 있는 책 입니다.
단점
Topcoder 플랫폼 자체가 좋게 말하면 고전, 나쁘게 말하면 -틀- 플랫폼 입니다.
설명 스타일이 호불호가 있습니다. 조금 투머치 성향입니다.
비추천 책 목록
아래 책들은 비추천 하는 책들 목록입니다.
위의 책들 만큼 길게 글을 적지 않도록 하겠습니다.
그렇다고 아예 쓻모가 없는 책은 아니라, 정보를 남기는 차원에서 간략히 적겠습니다.
다양한 예제로 학습하는 데이터 구조와 알고리즘 with C
저자: 나라심하 카루만치
제목부터 역하지만, 그래도 비추천 목록 중에서는 제일 쓸모 있는 책 입니다.
모든 데이터 구조를 깡으로, C로 구현하는 연습을 하는 책 입니다.
Cpp 아닙니다. “진짜” C 입니다.
Cpp STL 못 쓰는 삼성 코테 B형 대비용으로 아주 좋을것 같습니다.
알고리즘 트레이닝 북 (PROGRAMMING CHALLENGES)
저자: 스티븐 스키에나
그렇게 나쁜 책은 아닌데, 앞에 있는 책들에 비하면 좀 별로입니다.
가장 큰 단점은 재미가 없는 것 입니다.
내용에 큰 하자가 있는것은 아닌데, 이상하리만큼 재미가 없습니다.
스티븐 스키에나는 유명한 알고리즘 교과서 Algorithm Design Manual 의 저자입니다.
차라리 Algorithm Design Manual 을 읽는게 더 나을것 같습니다.
Data Structures & Algorithms in C++
옛-날(2017년) 데이터 구조 보조 교과서 였습니다.
돈 주고 산게 아까워서 버리지를 못하고 있습니다.
행여나 도서관에서 “Algorithm” 이라는 키워드로 책을 찾더라도 이건 꼭 거르시라고 남깁니다.
결론 Conclusion
읽어주셔서 감사합니다. 종만북 최고!