경쟁 프로그래머 핸드북 (2018) [PDF]

AI 요약

Antti Laaksonen이 쓴 《Competitive Programmer’s Handbook》은 프로그래밍 기초를 아는 독자를 대상으로 경쟁 프로그래밍과 알고리즘을 소개하는 책입니다. 2018년 7월 초안이며, 예제 코드는 C++11로 작성했습니다. 저자는 알고리즘 설계와 구현을 경쟁 프로그래밍의 두 축으로 설명합니다. 풀이 아이디어가 맞아도 구현이 정확하고 효율적이어야 테스트를 통과한다는 점을 짚습니다.

다루는 주제

책은 세 부분, 30개 장으로 구성됩니다. 기초 기법에서는 시간 복잡도, 정렬과 이진 탐색, 자료구조, 완전 탐색, 탐욕 알고리즘, 동적 계획법, 상환 분석, 구간 질의와 비트 연산을 다룹니다. 그래프 알고리즘 부분은 그래프 탐색과 최단 경로부터 트리 질의, 강한 연결 요소, 흐름과 컷까지 이어집니다. 고급 주제에서는 정수론, 조합론, 확률, 게임 이론, 문자열, 제곱근 분할 기법, 세그먼트 트리, 기하와 스위프 라인 알고리즘을 살펴봅니다.

예제로 익히는 알고리즘 설계

초반에는 입력과 출력, 정수 범위, 부동소수점 오차처럼 실제 구현에서 자주 만나는 주의점을 설명합니다. 시간 복잡도 장에서는 입력 크기에 따라 알고리즘이 얼마나 빠르게 처리되는지 추정하고, 제한 시간과 입력 크기를 함께 고려해 적절한 풀이를 고르는 방법을 보여줍니다. 예를 들어 최대 부분 배열 합 문제를 세 겹 반복문으로 푸는 O(n³) 풀이에서 시작해, 누적 계산으로 O(n²)로 줄이고, 각 위치에서 끝나는 최대 합을 갱신하는 O(n) 풀이까지 비교합니다. 이 과정에서 Kadane’s algorithm의 아이디어와 각 방식의 실행 시간 차이를 설명합니다.

정렬 장은 버블 정렬의 역전 수 분석, 병합 정렬의 O(n log n) 시간, 비교 기반 정렬의 하한을 다룹니다. 원소 값의 범위가 제한된 경우에는 계수 정렬로 O(n)에 정렬할 수 있다는 예도 제시합니다. C++ 표준 라이브러리의 sort 사용법과 사용자 정의 비교 연산자도 안내합니다. 각 주제는 개념만 나열하기보다 문제 풀이에서 어떤 기법을 적용하는지 코드와 분석을 함께 보여주는 구성입니다.

Hacker News 반응

독자들은 책의 접근성과 활용처, 경쟁 프로그래밍을 실무와 면접 준비에 연결할 수 있는지를 이야기했습니다. 알고리즘 문제 풀이를 사고력을 유지하는 연습으로 보는 의견과, 실무 문제와 거리가 있다는 지적이 함께 나왔습니다.

• @xendo — 이 책은 꽤 어려운 편입니다. 재치 있고 간결한 풀이 때문에 가독성을 조금 희생합니다. 저는 거의 비슷한 내용을 더 쉽게 설명하는 Zingaro의 《Algorithmic Thinking》이 더 편하게 읽혔습니다.
  • @gwbas1c — 늘 같은 약어를 쓰면 본인에게는 읽기 쉬워집니다. 이 코드는 대회용으로 한 번 쓰고 버리는 코드입니다. 다른 사람이 유지보수하거나 5년 뒤에 다시 열어볼 일을 걱정할 필요가 없습니다.
  • @yuye — ICPC 대회 심판을 몇 번 맡았습니다. 각 문제의 첫 정답 제출은 항상 직접 확인했습니다. 여기 나온 코딩 스타일은 상위권 팀에서 매우 흔합니다.
• @Keegs — 이 책을 정말 좋아합니다. 알고리즘 참고서로도, 코딩 면접 준비용으로도 좋습니다. 면접을 본 지는 꽤 됐지만 지난 5년 사이에 내용이 크게 달라졌을 것 같지는 않습니다.
  • @BeetleB — 코딩 면접 준비로 읽었습니다. 돌이켜보면 그 목적에는 별 도움이 되지 않았습니다. 그래도 꽤 많이 배웠고, 모두에게 추천합니다. 글도 잘 썼습니다.
  • @brcmthrowaway — 실제로는 무엇이 도움이 됐나요?
• @ExciteByte — 더 다듬은 판본이 있습니다. 이 책과 함께 풀기 좋은 문제 모음도 있습니다.
• @lifeisloving — AI 에이전트를 매일 많이 쓰다가 머리를 식히려고 Codeforces, Rosalind, Codewars, LeetCode를 틈틈이 풀고 있습니다. LLM에 지나치게 의존하면서 잊었거나 시간이 지나며 놓친 것을 많이 다시 배우고 있습니다. 정말 재미있습니다. 깊이 생각하고 답을 찾아내는 기분이 그리웠습니다. 우리 종이 그 욕구를 잃지 않으면 좋겠습니다.
  • @yuye — LLM의 확산을 보면 대부분은 배우고 싶어 하지 않는다는 점이 꽤 잘 드러났다고 생각합니다. 그런 욕구가 있는 사람은 원래 소수였습니다.
  • @goosejuice — 지식 노동 전반의 비용을 낮추는 기술이 등장했다는 사실만으로, 인간 중 배우거나 취미를 즐기려는 사람이 소수라고 결론 내리나요?
• @oleggromov — 저는 경쟁 프로그래머는 아니고 될 생각도 없지만, 이 책은 유용한 알고리즘을 실용적으로 익히는 좋은 입문서처럼 보입니다. 정말 좋습니다.

원문: Hacker News / 번역·요약: Trawling