문제 해결력을 높이는 알고리즘과 자료 구조 (코딩 테스트, 프로그래밍 경진대회 전 필독서!)

문제 해결력을 높이는 알고리즘과 자료 구조 (코딩 테스트, 프로그래밍 경진대회 전 필독서!)

$24.44
Description
알고리즘 문제의 답을 스스로 생각하는, 코딩 테스트와 프로그래밍 경진대회 전 필독서!
이 책은 알고리즘 입문서이자 + 응용력, 문제 해결력을 높여주는 알고리즘 활용서다. 궁극적으로 알고리즘을 잘 다룰 수 있게 실력을 키우는 것을 목표로 한다. 우선 알고리즘에 대해 전혀 모르는 사람이 알고리즘의 전반적인 모습을 체계적으로 인식하고, 필요한 기초 개념과 기본적인 알고리즘을 배울 수 있다. 알고리즘을 설명할 때는 유명한 알고리즘을 단순히 소개하는 것이 아니라 어떻게 설계되었는지 설계 기법과 설계 과정, 응용 방법과 사례도 함께 설명한다. 또한, 다양한 상황에서 알고리즘을 사용해 문제를 해결할 수 있도록 알고리즘을 설계할 때 필요한 지식과 접근법을 설명한다. 목표는 알고리즘의 동작을 구체적으로 이해하고 실제 문제 해결에 사용하는 것이며, 알고리즘을 단순히 아는 것을 넘어서 잘 다루는 것이다. 우리는 알고리즘을 사용해 주어진 문제를 잘 풀기도 하고, 내가 직접 설계도 하고, 더 효율적으로 개선할 수도 있어야 한다. 이 책은 이를 위해 필요한 방법과 지식을 학습한다.
저자

오츠키켄스케

석사(정보이공학)2014년도쿄대학대학원정보이공학계연구과수리정보학전공,석사과정수료2015년주식회사NTT데이터수리시스템연구원현재주식회사NTT데이터수리시스템고문TwitterID|@drken1215

목차

1장알고리즘이란?
1.1알고리즘이란무엇인가?
1.2알고리즘예제(1):깊이우선탐색과너비우선탐색
__1.2.1빈칸채우기퍼즐로배우는깊이우선탐색
__1.2.2미로로배우는너비우선탐색
1.3알고리즘예제(2):매칭
1.4알고리즘서술방법
1.5알고리즘을배우는의미
1.6연습문제

2장복잡도와빅오표기법
2.1복잡도란?
2.2복잡도와빅오표기법
__2.2.1복잡도빅오표기법생각해보기
__2.2.2코드2-1의복잡도
__2.2.3코드2-2의복잡도
__2.2.4실제로복잡도구해보기
__2.2.5복잡도를빅오표기법으로표시하는이유
2.3복잡도를구하는예(1):짝수나열
2.4복잡도를구하는예(2):최근접점쌍문제
2.5복잡도사용법
2.6복잡도관련주의사항
__2.6.1시간복잡도와공간복잡도
__2.6.2최악시간복잡도와평균시간복잡도
2.7란다우빅오표기법상세설명(*)
__2.7.1란다우빅오표기법
__2.7.2오메가표기법
__2.7.3세타표기법
2.8마무리
2.9연습문제

3장설계기법(1):전체탐색
3.1전체탐색을배우는의미
3.2전체탐색(1):선형탐색법
3.3선형탐색법의응용
__3.3.1조건을만족하는위치파악가능
__3.3.2최솟값구하기
3.4전체탐색(2):쌍전체탐색
3.5전체탐색(3):조합전체탐색(*)
3.6정리
3.7연습문제

4장설계기법(2):재귀와분할정복법
4.1재귀란무엇인가?
4.2재귀사용예(1):유클리드호제법
4.3재귀사용예(2):피보나치수열
4.4메모이제이션동적계획법
4.5재귀사용예(3):재귀함수를사용한전체탐색
__4.5.1부분합문제
__4.5.2부분합문제에대한재귀적전체탐색복잡도(*)
__4.5.3부분합문제에대한메모이제이션(*)
4.6분할정복법
4.7정리
4.8연습문제

5장설계기법(3):동적계획법
5.1동적계획법이란?
5.2동적계획법예제
5.3동적계획법관련개념도
__5.3.1완화
__5.3.2끌기전이형식과밀기전이형식
__5.3.3끌기전이형식과밀기전이형식비교
__5.3.4전체탐색메모이제이션을이용한동적계획법
5.4동적계획법예제(1):냅색문제
5.5동적계획법예제(2):편집거리
5.6동적계획법예제(3):구간분할최적화
5.7정리
5.8연습문제

6장설계기법(4):이진탐색법
6.1배열이진탐색
__6.1.1배열이진탐색
__6.1.2배열이진탐색복잡도(*)
6.2C++의std::lower_bound()
6.3일반화한이진탐색법
6.4좀더일반화한이진탐색법(*)
6.5응용예(1):나이맞히기게임
6.6응용예(2):std::lower_bound()활용
6.7응용예(3):최적화문제를판정문제로바꾸기
6.8응용예(4):중앙값구하기
6.9정리
6.10연습문제

7장설계기법(5):탐욕법
7.1탐욕법이란?
7.2탐욕법으로최적해를구할수없는경우
7.3탐욕법패턴(1):교환해도악화되지않음
7.4탐욕법패턴(2):현재가좋으면미래도좋음
7.5정리
7.6연습문제

8장자료구조(1):배열,연결리스트,해시테이블
8.1자료구조를배우는의미
8.2배열
8.3연결리스트
8.4연결리스트삽입과삭제
__8.4.1연결리스트삽입
__8.4.2연결리스트삭제
8.5배열과연결리스트비교
8.6해시테이블
__8.6.1해시테이블만드는법
__8.6.2해시충돌대책
__8.6.3해시테이블복잡도
__8.6.4C++와파이썬의해시테이블
__8.6.5연상배열
8.7정리
8.8연습문제

9장자료구조(2):스택과큐
9.1스택과큐의개념
9.2스택과큐의동작과구현
__9.2.1스택동작과구현
__9.2.2큐동작과구현
9.3정리
9.4연습문제

10장자료구조(3):그래프와트리
10.1그래프
__10.1.1그래프사고방식
__10.1.2유향그래프와무향그래프
__10.1.3워크,사이클,패스
__10.1.4연결성
10.2그래프를사용하는공식화예시
__10.2.1소셜네트워크
__10.2.2교통네트워크
__10.2.3게임국면전이
__10.2.4작업의존관계
10.3그래프구현
10.4가중그래프구현
10.5트리
__10.5.1루트트리
__10.5.2부분트리와트리높이
10.6순서트리와이진트리
__10.6.1순서트리와이진트리
__10.6.2강균형이진트리
10.7이진트리를사용한자료구조예(1):힙
__10.7.1힙이란?
__10.7.2힙실현방법
__10.7.3힙쿼리처리
__10.7.4힙구현예
__10.7.5O(N)복잡도로힙구축(*)
10.8이진트리를사용하는자료구조예(2):이진탐색트리
10.9정리
10.10연습문제

11장자료구조(4):Union-Find
11.1Union-Find란?
11.2Union-Find구조
11.3Union-Find복잡도를줄이는방법
11.4Union-Find개선법1:unionbysize
__11.4.1unionbysize란?
__11.4.2unionbysize복잡도분석
11.5Union-Find개선법2:경로압축
11.6Union-Find구현
11.7Union-Find응용:그래프연결요소개수
11.8정리
11.9연습문제

12장정렬
12.1정렬이란?
12.2정렬알고리즘의좋고나쁨
__12.2.1in-place와안정성
__12.2.2어떤정렬알고리즘이좋은가?
12.3정렬(1):삽입정렬
__12.3.1동작과구현
__12.3.2삽입정렬복잡도와성질
12.4정렬(2):병합정렬
__12.4.1동작과구현
__12.4.2병합정렬복잡도와성질
__12.4.3병합정렬복잡도를자세히분석하기(*)
12.5정렬(3):퀵정렬
__12.5.1동작과구현
__12.5.2퀵정렬복잡도와성질
__12.5.3무작위선택퀵정렬(*)
12.6정렬(4):힙정렬
12.7정렬복잡도의하한값
12.8정렬(5):버킷정렬
12.9정리
12.10연습문제

13장그래프(1):그래프탐색
13.1그래프탐색을배우는의의
13.2깊이우선탐색과너비우선탐색
13.3재귀함수를사용하는깊이우선탐색
13.4전위순회와후위순회
13.5최단경로알고리즘으로너비우선탐색
13.6깊이우선탐색과너비우선탐색의복잡도
13.7그래프탐색예(1):s-t패스구하기
13.8그래프탐색예(2):이분그래프판정
13.9그래프탐색예(3):위상정렬
13.10그래프탐색예(4):트리동적계획법(*)
13.11정리
13.12연습문제

14장그래프(2):최단경로문제
14.1최단경로문제란?
__14.1.1가중치유향그래프
__14.1.2단일시작점최단경로문제
__14.1.3음의변과음의닫힌경로
14.2최단경로문제정리
14.3완화
14.4DAG의최단경로문제:동적계획법
14.5단일시작점최단경로문제:벨만-포드알고리즘
__14.5.1벨만-포드알고리즘아이디어
__14.5.2벨만-포드알고리즘구현
__14.5.3벨만-포드알고리즘의정확성(*)
14.6단일시작점최단경로문제:다익스트라알고리즘
__14.6.1두종류의다익스트라알고리즘
__14.6.2단순한다익스트라알고리즘
__14.6.3다익스트라알고리즘의직감적인이미지
__14.6.4다익스트라알고리즘정확성(*)
__14.6.5희소그래프인경우:힙을사용한고속화(*)
14.7모든쌍의최단경로문제:플로이드-워셜알고리즘
14.8참고:포텐셜과차분제약계(*)
14.9정리
14.10연습문제

15장그래프(3):최소신장트리문제
15.1최소신장트리문제란?
15.2크러스컬알고리즘
15.3크러스컬알고리즘구현
15.4신장트리구조
__15.4.1컷
__15.4.2기본사이클
__15.4.3기본컷집합
15.5크러스컬알고리즘의정확성(*)
15.6정리
15.7연습문제

16장그래프(4):네트워크흐름
16.1네트워크흐름을배우는의의
16.2그래프연결도
__16.2.1변연결도
__16.2.2최소컷문제
__16.2.3변연결도를구하는알고리즘과강쌍대성증명
16.3최대흐름문제와최소컷문제
__16.3.1최대흐름문제란?
__16.3.2흐름의성질
__16.3.3최소컷문제와쌍대성
__16.3.4포드-풀커슨알고리즘
16.4포드-풀커슨알고리즘구현
16.5응용예(1):이분매칭
16.6응용예(2):점연결도
16.7응용예(3):프로젝트선택문제
16.8정리
16.9연습문제

17장P와NP
17.1문제의어려움을측정하는방법
17.2P와NP
17.3P≠NP문제
17.4NP완전
17.5다항식시간환원예
__17.5.1꼭짓점커버문제
__17.5.2부분합문제(*)
17.6NP난해
17.7정지문제
17.8정리
17.9연습문제

18장어려운문제대책
18.1NP난해문제와마주하기
18.2특수한경우로풀리는방법
18.3탐욕법
18.4국소탐색과담금질기법
18.5분기한정법
18.6정수계획문제로공식화
18.7근사알고리즘
18.8정리
18.9연습문제

19장참고문헌
19.1알고리즘전반
19.2알고리즘전반(본격적인전문서)
19.3복잡도,P와NP
19.4그래프알고리즘,조합최적화
19.5어려운문제대책
19.6기타분야

후기
찾아보기

출판사 서평

알고리즘문제를풀수있다!
더나아가,설계하고개선하고확장하여새로운무언가를생각해낼수있다!

컴퓨터과학을배운다면피할수없는알고리즘
알고리즘이란문제를풀기위한절차다.알고리즘을배운다는건단순히이론을외우는것이아닌세상의다양한문제를해결하는수단을늘려가는것을말한다.알고리즘을잘다뤄서제시된문제를잘풀고싶다면?내가직접알고리즘을설계하고더효율이높게개선하고싶다면?이를위해서는어떤알고리즘이있는지알기만하는데서그치지않고설계하고응용하는과정을학습해야한다.알고리즘동작을구체적으로이해하는걸넘어서,실제로알고리즘을활용하여문제를만족스럽게해결할때비로소알고리즘을배웠다고할수있다.

설계기법을중시하면서알고리즘전체를체계적으로설명
이책은문제의답을스스로찾아내고,알고리즘지식을확실히자신의것으로만들어활용하는것을목표로한다.이를위해먼저알고리즘을설계할때필요한접근법(설계기법)을상세히설명하고,이어서설계한알고리즘을효과적으로실현하는데있어서중요한자료구조를살펴본다.그리고앞에서배운설계기법과자료구조를활용하여정렬알고리즘과그래프알고리즘을배운다.마지막으로효율적으로풀수있는알고리즘을설계할수없는난제를판별하는방법과이에대응하는방법을살펴본다.

쉬운문장,쉬운코드,재미있는그림,어려운내용도간단히이해
어려운수식,복잡한내용은담지않았다.중학수학과최소한의C++지식만있으면알고리즘의기초를체계적으로익힐수있다.설계기법에중점을둔설명은입문자뿐만아니라중급자레벨에도추천한다.핵심개요,일반화,좋은예와나쁜예,응용예,주의점등을단계별로구성하고,여러측면에서알고리즘사고법과기술을살펴본다.알고리즘,자료구조를시각적으로이해할수있도록그림도풍부하게사용했다.코드는의사코드가아닌C++코드를사용했으며,코드또한읽기쉽고이해하기쉽도록명확하게작성하고자했다.

이책에서다루는내용
단순히알고리즘동작을설명하기보다는좋은알고리즘을설계하는방법에중점을둡니다.알고리즘을처음배우는분부터실용적인알고리즘설계기법을배우고싶은분까지폭넓게즐길수있으면좋겠습니다.

필요한예비지식
고등학교수학을배웠고프로그래밍경험이있다고전제합니다.복잡한수학적이해가필요한부분도있는데,초보자에게어려운내용은(*)기호로표시했습니다.
책에나오는소스코드는C++로작성했는데,기본기능만사용하므로프로그래밍경험이있다면큰문제없이읽을수있습니다.C++의고유기능중다음을사용합니다.
-std::vector같은STL컨테이너
-std::sort()같은표준라이브러리
-const수식자
-템플릿
-포인터
-참조
-구조체

사용하는언어
이책은C++를사용해서알고리즘을작성하며,다음과같은C++11이후기능을일부사용합니다.
-범위for문
-auto를사용한타입추론(범위for문에서만사용)
-std::vectorv={1,2,3};같은vector형변수초기화
-using을사용한자료형별명선언
-템플릿오른쪽괄호에공백생략
-std::sort()복잡도가O(NlogN)이라는것이보증됨

동작환경
이책에실린소스코드는C++11이후버전의C++에서컴파일가능하고,Wandbox에서gcc9.2.0으로코드동작을확인했습니다.(번역시macOSBigSurclang12.0.0버전에서확인)
소스코드는다음주소에서다운로드가능합니다.
-저자깃허브:https://github.com/drken1215/book_algorithm_solution
-길벗깃허브:https://github.com/gilbutITbook/080288