(ACM ICPC, IOI/KOI) 알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우

By | 2017년 6월 5일

알고리즘 트레이닝』 스티븐 할림•펠릭스 할림 지음 | 김진현 옮김 | 656쪽

또 하나의 야무지고 단단한 알고리즘 책
인사이트에서 발간한 알고리즘 학습서의 대명사인 『알고리즘 문제 해결 전략』부터 『코딩 인터뷰 완전 분석』, 『문제로 풀어보는 알고리즘』, 『다양한 예제로 학습하는 데이터 구조와 알고리즘』, 『다양한 예제로 학습하는 데이터 구조와 알고리즘 for Java』 등에 이어 또 하나의 야무지고 단단한 알고리즘 서적이 출간됩니다.

바로 『(ACM ICPC, IOI/KOI) 알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우』입니다. 🙂

프로그래밍 대회 준비 전략서
이 책은 프로그래밍 대회에 등장할 법한 자료 구조와 알고리즘을 프로그래밍 연습 문제와 함께 소개하고 있습니다. 경진 프로그래밍과 관련된 경험이 전혀 없는 이들을 위한 내용도 다루고, ACM ICPC 세계 결선에서 어쩌다 한 번 만날 수 있을 법한 몹시 어려운 내용도 다룹니다. 어떤 수준의 독자도 읽을 만한 책이지만, 입문서 한 권을 공부한 후(혹은 공부하면서) 내용을 복습하면서 문제를 많이 풀어보고 싶은 독자들에게 특히 유용할 것입니다. 이론적인 내용과 바로 연결되는 프로그래밍 문제가 1,600개 이상 소개되어 있기 때문입니다.

문제 해결 능력과 효과적인 코드를 구현하는 방법 
이 책은 자료 구조 및 알고리즘에 대한 기본 지식을 바탕으로 국내외 프로그래밍 경진대회나 각종 알고리즘 테스트를 대비해 문제 해결 능력과 효과적인 코드 구현 방법을 훈련할 수 있도록 구성되어 있는데요. 프로그래밍 기법에 대해 기본적인 내용을 알고 있고, 프로그래밍 언어 중 적어도 하나(C•C++ 혹은 Java)에는 능숙하고, 자료 구조 및 알고리즘, 간단한 알고리즘 분석을 이해하고 있는 수준인 독자라면 한 걸음 더 나아가 세계적인 수준의 훌륭한 프로그래머로 도약해보고 싶은 욕심이 나는 게 인지상정일 듯합니다. 그렇다면 일단 이 책에 나오는 내용에 능숙해지는 연습을 해보는 건 어떨까요?

이 책의 대상 독자
『알고리즘 트레이닝』은 앞서 말씀드린 대로 초보 프로그래머를 대상으로 쓰인 책은 아닙니다. 하지만 다음의 독자들이라면 이 책을 필독서로 선택하시길 권합니다.

  • 매년 개최되는 ACM ICPC(International Collegiate Programming Contest, 국제 대학생 프로그래밍 경시대회) 지역 대회(혹은 세계 결선)에 참가하는 대학생
  •  매년 개최되는 IOI(International Olympiad in Informatics, 국제 정보 올림피아드) 혹은 국내 전국 대회나 지역 대회에 참가하는 중고등학생
  • 사내 소프트웨어 역량 테스트를 준비하는 프로그래머
  • 학생들을 지도할 때 쓸 종합적 연습 자료를 구하고 있는 지도자
  • 컴퓨터 프로그램을 이용하여 문제 풀기를 좋아하는 사람
  • 그 외의 프로그래밍 대회 참가자. 예를 들면 탑코더 오픈(TopCoder Open), 구글 코드잼(Google CodeJam), IPSC(Internet Problem Solving Contest, 인터넷 문제 풀이 대회) 등

그렇다고 해서 이 책이 꼭 프로그래밍 대회를 준비하는 독자들에게만 유용한 책은 아닙니다. 가령 알고리즘 문제 해결과 관련된 시험이나 코딩 인터뷰를 준비하는 독자, 자료 구조나 알고리즘 이론을 공부한 후 직접 구현해보면서 내용을 자신의 것으로 만들고 싶은 독자들에게도 도움이 될 것입니다.

이 책을 번역하신 김진현 님은 중고등학생 때 올림피아드를 통해 경진 프로그래밍에 입문하셨다고 합니다. 학부 때는 학내에 ACM ICPC 참가를 위한 동아리를 만들었고 대학원 때는 틈틈이 Topcoder Open, Google Code Jam 등의 대회에 참가했던 경력으로 후배 독자들에게 이 책의 내용을 좀 더 꼼꼼히 전달하시려고 수고를 아끼지 않으셨습니다.

알고리즘 트레이닝 북
경진 프로그래밍(Competitive programming), 혹은 알고리즘 문제 해결(algorithmic problem solving)과 관련된 서적이 시중에 많이 나와 있습니다. 그러나 대부분은 입문자나 전문가를 위한 양극단의 책이고, 첫걸음을 뗀 이들이 몇 걸음 더 나아갈 수 있도록 도와주는 책은 그리 많지 않은 듯합니다. 문제를 많이 풀어보는 것이 가장 좋은 공부 방법이라는 사실을 알고 있지만, 실천에 옮기려고 할 때 부족한 의지가 아니라 막막한 마음이 발목을 잡는 경험을 해 본 분들, 문제의 풀이나 구현 방법을 몰라서 마냥 시간을 흘려보내기만 한 분들도 많이 있을 것입니다. 그런 분들께 이 책이 도움이 될 수 있으리라 생각합니다.
– ‘옮긴이의 글’ 중에서

이 책에서 다루는 내용
간략히 요약하면 다음과 같습니다.

  • 자료 구조와 라이브러리 목록
  • 여러 알고리즘의 구현 방법과 문제 해결 패러다임
  • 다양한 주제와 연습 문제, 프로그래밍 문제, 힌트와 간략 풀이
  • 문제 해결 능력과 창의력을 끌어올리는 데 중점을 두기
  • 푸는 방법(UVa 온라인 채점 사이트LA 라이브 아카이브) 공개
  • 이 책의 모든 프로그래밍 문제와 통합된 uhunt.felix-halim.net이라는 학습 도구 제공
  • 강의 슬라이드와 여러 알고리즘의 상호작용이 가능한 시각화 자료 제공

각 장별로 좀 더 살펴보겠습니다.

  • 1장 도입
    경진에 능숙해지기 위한 팁과 자주 사용되는 입출력 루틴 그리고 애드혹 문제
  • 2장 자료 구조와 라이브러리
    내장된 라이브러리가 있는 선형 자료 구조와 그래프, 유니온-파인드 상호 배타적 집합과 구간 트리 등 거의 모든 자료 구조에 대한 자세한 설명
  • 3장 문제 해결 패러다임
    완전 탐색 기법과 분할 정복, 탐욕법과 DP(Dynamic Programming, 동적 계획법), 고전적인 예제와 고전적이지 않은 예제 문제 등그림_이 절에서 다룬 고전적인 DP 문제에 대한 요약
  • 4장 그래프
    그래프 탐색과 최소 스패닝 트리, 단일 시작점 최단 경로와 네트워크 유량, 알고리즘 본래의 아이디어 등그림_두 번째 스패닝 트리(UVa 10600번 문제에 대한 내용)
  • 5장 수학
    애드혹 수학 문제와 JavaBigInteger 클래스, 조합론과 정수론, 확률론과 사이클 찾기 그리고 게임 이론 등
  • 6장 문자열 처리
    애드혹 문자열 처리 문제와 문자열 매칭, 접미사 트라이·트리·배열
  • 7장 (계산) 기하
    기본적인 도형과 라이브러리, 다각형 관련 알고리즘과 라이브러리
  • 8장 고급 주제
    고급 탐색 기법과 고급 DP 기법, 문제 분해하기 등
  • 9장 희귀한 주제
    2-SAT 문제, 미술관 문제, 바이토닉 여행하는 외판원 문제, 중국인 우편배달부 문제, 디닉 알고리즘, 하노이 탑 등

『알고리즘 트레이닝』을 추천해주신 분들의 이야기를 들려 드립니다.

독자의 프로그래밍 역량을 한 단계 높여줄 명저
많은 프로그래밍 관련 서적이 단순히 문제들과 그 풀이로 구성된 경우가 많은데 이 책은 문제들을 분류한 다음, 각 주제에 대한 기초 지식부터 소개한다. 정보 올림피아드로 훈련된 저자의 방대한 경험을 토대로 정성스럽고 효율적으로 쓴 명저다. 프로그래밍이라는 것은 단순히 프로그래밍 언어를 사용하는 기술이 아니고, 문제나 상황에 대한 체계적인 사고와 해법이 선행된 다음 마지막 절차인 구현 단계에서 프로그래밍 언어를 통할 뿐이다. 이 책은 여러 가지 주제에 대해 생각하는 방법, 생각의 기본을 제공하는 이론적 기초, 효율적으로 문제를 해결하는 팁 등을 제시해 독자들의 역량을 한 단계 높여줄 것이다.
– 문병로, 서울대학교 컴퓨터공학부 교수

경쟁력 있는 프로그래머가 되기 위한 문제 해결 전략서
세상의 거의 모든 일이 그렇지만, 더 훌륭한 경진 프로그래머가 되는 길에도 왕도는 없습니다. 어떤 좋은 설명과 친절한 강의도 스스로 문제를 풀며 꾸준히 쌓은 경험을 대체할 수는 없습니다. 하지만 인터넷에는 너무 많은 자료와 문제들이 있고, 자칫하다가 자료의 홍수에 빠져 시간을 낭비하기 쉽습니다. 이 점을 생각하면 바야돌리드(Valladolid) 채점 시스템의 엄청나게 많은 문제를 정리하고 분류해서 커리큘럼을 만든 이 책의 실용성이 두드러집니다. 당장 대회에서 써먹을 수 있는 실용적인 테크닉과 접근 방법들을 제시한 점도 눈에 띕니다. 문제 해결 능력에 대한 관심이 늘어나는 최근 추세에 또 하나의 훌륭한 책이 국내에 소개되어 기쁩니다. 많은 분에게 도움이 되기를 바랍니다.
– 구종만, 『알고리즘 문제 해결 전략』 저자

▶ 목차와 본문 미리보기를 확인하시려면 다음을 클릭하세요.
미리보기_알고리즘 트레이닝

▶ 이 책은 다음 서점에서 구입하실 수 있습니다.
Yes24 | 알라딘 | 인터파크 | 교보문고