알고리즘 트레이닝 : 자료 구조, 알고리즘 문제 해결 핵심 노하우

4차 산업혁명의 시작이 대두되며 인공지능, 소프트웨어, 사물인터넷의 등장과 함께 알고리즘 또한 각광받기 시작하고 있습니다만, 전공자가 아닌 이상 "알고리즘"이라는 분야는 아직 생소하기만 합니다. 컴퓨터 전공을 하는 사람들의, 그들만의 리그라고나 할까요?컴퓨터 전공을 하는 사람들에게도 쉽지 않은, 이 알고리즘 이라고 하는 분야에서 인사이트 출판사는 알고리즘 문제 해결 전략 이라는 아주 좋은 책을 이미 출판했음에도 불구하고 알고리즘 트레이닝 이라는 또 한권의 도서를 출간합니다.사실 개인적으로 알고리즘 문제 해결 전략 을 읽어본 사람으로써는 프로그래밍 언어에 대한 깊은 이해 뿐만 아니라 수학에 대한 대학 전공자 수준의 이해가 있지 않으면 난이도가 좀 있는 책이라고 생각합니다. 알고리즘 트레이닝 또한 마찬가지인데요. 책의 타겟 독자층 또한 알고리즘 입문자나 알고리즘 관련 대회 초급 수준의 독자들은 첫장부터 숨이 막힐 만큼 난이도가 다소 높을 수도 있습니다. 최소 알고리즘과 관련된 입문서 1~2권 정도와 함께 주로 사용할 프로그래밍 언어 도서 1권은 함께 하시면 좋을 것 같습니다.- 각 장별로 다루고 있는 내용(참조 : 인사이트 사이트http://www.insightbook.co.kr/archives/11923)1장 도입경진에 능숙해지기 위한 팁과 자주 사용되는 입출력 루틴 그리고 애드혹 문제2장 자료 구조와 라이브러리내장된 라이브러리가 있는 선형 자료 구조와 그래프, 유니온-파인드 상호 배타적 집합과 구간 트리 등 거의 모든 자료 구조에 대한 자세한 설명3장 문제 해결 패러다임완전 탐색 기법과 분할 정복, 탐욕법과 DP(Dynamic Programming, 동적 계획법), 고전적인 예제와 고전적이지 않은 예제 문제 등4장 그래프그래프 탐색과 최소 스패닝 트리, 단일 시작점 최단 경로와 네트워크 유량, 알고리즘 본래의 아이디어 등5장 수학애드혹 수학 문제와 JavaBigInteger 클래스, 조합론과 정수론, 확률론과 사이클 찾기 그리고 게임 이론 등6장 문자열 처리애드혹 문자열 처리 문제와 문자열 매칭, 접미사 트라이·트리·배열7장 (계산) 기하기본적인 도형과 라이브러리, 다각형 관련 알고리즘과 라이브러리8장 고급 주제고급 탐색 기법과 고급 DP 기법, 문제 분해하기 등9장 희귀한 주제2-SAT 문제, 미술관 문제, 바이토닉 여행하는 외판원 문제, 중국인 우편배달부 문제, 디닉 알고리즘, 하노이 탑 등내용 자체는 번역서임에도 불구하고 굉장히 깔끔하고 잘 정렬되어 있습니다. 각 장별로 개요 및 동기를 통해 대회의 어떤 부분에서 해당 알고리즘이 사용되는지(혹은 난이도나 출제 빈도 등) 안내하고 있으며, 이는 알고리즘 트레이닝 을 바탕으로 학생들을 가르치는 교사나 강사, 교수 등의 분들에게 매우 유용할 것으로 보입니다.또한 UVa와 연계하여 약 1600여개의 예제 및 힌트, 문제 풀이, 자료 구조와 라이브러리 목록을 제공하기 때문에 독자들에게 정답을 맞춰 볼 것을 강요(?)하는 일부 도서들과는 달리 필요한 알고리즘 부분을 찾아보고 공부할 수 있는 장점이 있습니다. 그러나 책 자체가 매우 두껍기 때문에(600페이지가 넘는 분량) 찾아보실 때는 반드시 목차를 보셔야 알 수 있습니다.다만 외국 원서에 대한 번역본이라 그런지 전반적으로 ACM-ICPC에 대한 이야기가 많이 나오며(이 부분은 다른 분의 리뷰에서도 찾아볼 수 있었습니다) 책을 읽는 독자들에겐 다소 괴리감이 느껴질 수도 있습니다.워낙 방대한 양에 약 2주 정도의 시간임에도 많은 부분을 보진 못했지만 알고리즘과 자료구조에 대해 사전 지식을 갖춘 학생의 말로는 지금까지 봤던 알고리즘 책 중에서 굉장히 상세하고 깊이 있는 내용을 다루고 있다는 이야기를 들을 수 있었습니다. 또한 국내 알고리즘 대회를 준비하고 있는 입장에서 기존의 알고리즘 책에서 이론만 다루었던 부분이나 두루뭉술하게 넘어갔던 부분들에 대해 짚어보고 실제로 예제와 힌트를 바탕으로 다뤄볼 수 있어 알고리즘의 바이블(!)이라 불려도 손색없을 것 같다는 감탄사도 곁들였습니다.자료구조와 알고리즘을 공부할 수록 "어렵다"는 생각이 매번 듭니다. 책에 나와있는 것보다 더 간결하거나 더 쉽게 풀어낼 수 있는 문제들도 많이 존재하겠지요. 사람마다 풀어내는 방법이 다르기에 알고리즘이 잡힐 듯 하면서 잡히지 않는 이유도 그 때문일 것입니다.그런 분들에게 알고리즘 트레이닝 이 어쩌면 알고리즘에 대한 가이드 북으로써 이해를 돕고, 문제를 해결하는 하나의 방법(혹은 힌트)을 제시함으로써 다른 여러 방법으로 해결할 수 있는 실마리를 제공할 수 있지 않을까? 라는 생각을 해 봅니다. 또한 국내외 경진대회를 준비하거나 한 단계 도약이 필요한 프로그래머 혹은 학생, 알고리즘 관련 교육이 필요한 교수자에게도 충분한 도움이 될 수 있는 책이라고 생각합니다.본 리뷰는 도서출판 인사이트에서 제공된 책으로 작성하였습니다.http://www.insightbook.co.kr
Competitive Programming
자료 구조 및 알고리즘에 대한 기본 지식을 바탕으로
국내외 프로그래밍 경진대회나 각종 알고리즘 테스트를 대비해
문제 해결 능력과 효과적인 코드 구현 방법을 훈련할 수 있도록 구성된 책

독자의 프로그래밍 역량을 한 단계 높여줄 명저

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

옮긴이의 글
추천사
머리글
약어 목록

1장 도입
1.1 경진 프로그래밍
1.2 경진에 능숙해지기 위한 팁
1.2.1 1번 팁: 빠른 속도로 코딩하자!
1.2.2 2번 팁: 문제 유형을 빠르게 파악하자
1.2.3 3번 팁: 알고리즘 분석을 수행하자
1.2.4 4번 팁: 프로그래밍 언어에 능숙해지자
1.2.5 5번 팁: 코드를 테스트하는 기술에 능숙해지자
1.2.6 6번 팁: 연습하고 또 연습하자
1.2.7 7번 팁: (ICPC를 위한) 팀워크
1.3 첫걸음 떼기: 쉬운 문제들
1.3.1 프로그래밍 대회 문제 뜯어보기
1.3.2 자주 사용되는 입출력 루틴
1.3.3 여정의 시작
1.4 애드혹 문제
1.5 별표가 없는 연습 문제에 대한 풀이
1.6 이 장을 마치며

2장 자료 구조와 라이브러리
2.1 개요 및 동기
2.2 내장된 라이브러리가 있는 선형 자료 구조
2.3 내장된 라이브러리가 있는 비선형 자료 구조
2.4 자체적인 라이브러리가 필요한 자료 구조
2.4.1 그래프
2.4.2 유니온-파인드 상호 배타적 집합
2.4.3 구간 트리
2.4.4 이진 인덱스 트리(펜윅 트리)
2.5 별표가 없는 연습 문제에 대한 풀이
2.6 이 장을 마치며

3장 문제 해결 패러다임
3.1 개요 및 동기
3.2 완전 탐색
3.2.1 반복적 완전 탐색
3.2.2 재귀적 완전 탐색
3.2.3 팁
3.3 분할 정복
3.3.1 이진 탐색의 흥미로운 활용 예
3.4 탐욕법
3.4.1 예제
3.5 DP
3.5.1 DP의 예
3.5.2 고전적인 예제 문제들
3.5.3 고전적이지 않은 예제 문제
3.6 별표가 없는 연습 문제에 대한 풀이
3.7 이 장을 마치며

4장 그래프
4.1 개요 및 동기
4.2 그래프 탐색
4.2.1 깊이 우선 탐색
4.2.2 너비 우선 탐색
4.2.3 연결된 컴포넌트 구하기(무방향 그래프)
4.2.4 플러드 필(연결된 컴포넌트에 번호를 붙이거나 색칠하기)
4.2.5 위상 정렬(사이클 없는 방향 그래프)
4.2.6 이분 그래프 검사
4.2.7 DFS 스패닝 트리를 이용한 그래프의 간선 속성 검사
4.2.8 절단점 및 다리 구하기(무방향 그래프)
4.2.9 강결합 컴포넌트 구하기(방향 그래프)
4.3 최소 스패닝 트리
4.3.1 개요 및 동기
4.3.2 크루스칼 알고리즘
4.3.3 프림 알고리즘
4.3.4 몇 가지 활용 예
4.4 단일 시작점 최단 경로
4.4.1 개요 및 동기
4.4.2 가중치 없는 그래프에 대한 단일 시작점 최단 경로
4.4.3 가중치 그래프에 대한 단일 시작점 최단 경로
4.4.4 음수 사이클이 존재하는 그래프에 대한 단일 시작점 최단 경로
4.5 모든 쌍 최단 경로
4.5.1 개요 및 동기
4.5.2 플로이드-워셜의 DP 풀이에 대한 설명
4.5.3 몇 가지 활용 예
4.6 네트워크 유량
4.6.1 개요 및 동기
4.6.2 포드-풀커슨 기법
4.6.3 에드몬드-카프 알고리즘
4.6.4 유량 그래프 모델링 - 1부
4.6.5 몇 가지 활용 예
4.6.6 유량 그래프 모델링 - 2부
4.7 특수 그래프
4.7.1 사이클 없는 방향 그래프
4.7.2 트리
4.7.3 오일러 그래프
4.7.4 이분 그래프
4.8 별표가 없는 연습 문제에 대한 풀이
4.9 이 장을 마치며

5장 수학
5.1 개요 및 동기
5.2 애드혹 수학 문제
5.3 Java BigInteger 클래스
5.3.1 기본 기능
5.3.2 부가 기능
5.4 조합론
5.4.1 피보나치 수
5.4.2 이항 계수
5.4.3 카탈란 수
5.4.4 프로그래밍 대회에서의 조합론에 대한 첨언
5.5 정수론
5.5.1 소수
5.5.2 최대공약수와 최소공배수
5.5.3 팩토리얼
5.5.4 최적화된 나눗셈 시도 방법으로 소인수 구하기
5.5.5 소인수 다루기
5.5.6 소인수를 다루는 함수
5.5.7 수정된 체
5.5.8 모듈로 연산
5.5.9 확장된 유클리드 알고리즘: 선형 디오판토스 방정식 풀기
5.5.10 프로그래밍 대회에서의 정수론에 대한 첨언
5.6 확률론
5.7 사이클 찾기
5.7.1 효율적인 자료 구조를 사용하는 풀이
5.7.2 플로이드의 사이클 찾기 알고리즘
5.8 게임 이론
5.8.1 결정 트리
5.8.2 풀이가 빨라지도록 하기 위한 수학적 통찰
5.8.3 님 게임
5.9 별표가 없는 연습 문제에 대한 풀이
5.10 이 장을 마치며

6장 문자열 처리
6.1 개요 및 동기
6.2 기본적 문자열 처리 기법
6.3 애드혹 문자열 처리 문제
6.4 문자열 매칭
6.4.1 라이브러리를 이용한 풀이
6.4.2 KMP 알고리즘
6.4.3 2차원 격자에 대한 문자열 매칭
6.5 동적 계획법을 이용한 문자열 처리
6.5.1 문자열 정렬(편집 거리)
6.5.2 최장 공통 부분 수열
6.5.3 DP로 풀 수 있는 고전적이지 않은 문자열 처리 문제
6.6 접미사 트라이?트리?배열
6.6.1 접미사 트라이 및 그 활용 예
6.6.2 접미사 트리
6.6.3 접미사 트리의 활용 예
6.6.4 접미사 배열
6.6.5 접미사 배열의 활용 예
6.7 별표가 없는 연습 문제에 대한 풀이
6.8 이 장을 마치며

7장 (계산) 기하
7.1 개요 및 동기
7.2 기본적인 도형 및 라이브러리
7.2.1 0차원 도형: 점
7.2.2 1차원 도형: 직선
7.2.3 2차원 도형: 원
7.2.4 2차원 도형: 삼각형
7.2.5 2차원 도형: 사각형
7.3 다각형 관련 알고리즘 및 라이브러리
7.3.1 다각형의 표현법
7.3.2 다각형의 둘레
7.3.3 다각형의 면적
7.3.4 다각형이 볼록한지 검사하기
7.3.5 어떤 점이 다각형 내부에 있는지 검사하기
7.3.6 다각형을 직선으로 자르기
7.3.7 점들의 집합의 볼록 껍질 구하기
7.4 별표가 없는 연습 문제에 대한 풀이
7.5 이 장을 마치며

8장 고급 주제
8.1 개요 및 동기
8.2 고급 탐색 기법
8.2.1 비트마스크를 이용한 퇴각 검색
8.2.2 가지치기를 많이 사용한 퇴각 검색
8.2.3 BFS나 다익스트라 알고리즘을 이용한 상태 공간 탐색
8.2.4 중간 만남 기법(양방향 탐색)
8.2.5 정보 탐색(A*와 IDA*)
8.3 고급 DP 기법
8.3.1 비트마스크를 이용한 DP
8.3.2 자주 사용되는 (DP) 인자 모음
8.3.3 오프셋 기법을 이용하여 인자의 값이 음수인 경우 처리하기
8.3.4 MLE? 메모 테이블로 균형 잡힌 이진 검색 트리를 사용하는 것을 검토해보자
8.3.5 MLE?TLE? 더 나은 상태 표현법을 사용하자
8.3.6 MLE?TLE? 인자를 하나 생략하고 다른 인자들을 사용하여 이를 복구하자
8.4 문제 분해하기
8.4.1 두 가지 요소: 답에 대한 이진 탐색과 다른 요소
8.4.2 두 가지 요소: 정적인 1차원 구간 합?최소?최대 질의 사용하기
8.4.3 두 가지 요소: 그래프 사전 처리와 DP
8.4.4 두 가지 요소: 그래프를 다루는 문제
8.4.5 두 가지 요소: 수학을 다루는 문제
8.4.6 두 가지 요소: 완전 탐색과 기하
8.4.7 두 가지 요소: 효율적인 자료 구조 사용하기
8.4.8 세 가지 요소
8.5 별표가 없는 연습 문제에 대한 풀이
8.6 이 장을 마치며

9장 희귀한 주제
9.1 개요 및 동기
9.2 2-SAT 문제
9.3 미술관 문제
9.4 바이토닉 여행하는 외판원 문제
9.5 괄호 짝 맞추기
9.6 중국인 우편배달부 문제
9.7 가장 가까운 쌍 문제
9.8 디닉 알고리즘
9.9 공식 및 정리
9.10 가우스 소거법 알고리즘
9.11 그래프 매칭
9.12 대원 거리
9.13 홉크로프트-카프 알고리즘
9.14 독립적이거나 간선이 상호 배타적인 경로
9.15 반전 인덱스
9.16 조세푸스 문제
9.17 나이트의 이동
9.18 코사라주 알고리즘
9.19 최소 공통 조상
9.20 (홀수 크기의) 마방진 만들기
9.21 행렬 곱셈 순서 문제
9.22 행렬의 거듭제곱
9.23 최대 가중치 독립 집합
9.24 최소 비용 (최대) 유량
9.25 DAG에 대한 최소 경로 덮개
9.26 팬케이크 정렬
9.27 폴라드 로 정수 소인수분해 알고리즘
9.28 후위 표현식 계산하기 및 변환하기
9.29 로마 숫자
9.30 선택 문제
9.31 더 빠른 최단 경로 알고리즘
9.32 슬라이딩 윈도
9.33 선형 시간 정렬
9.34 희소 테이블 자료 구조
9.35 하노이 탑
9.36 이 장을 마치며

부록 A uHunt

부록 B 문제 저작자

참고자료
찾아보기