코딩 테스트를 위한 자료 구조와 알고리즘 with C++ (67개 문제 풀이로 익히자!)

존캐리

JohnCarey
작곡가이자피아니스트이며,음악적영역에기반한정규교육과정을밟았다.자신의예술활동에서컴퓨터와다양한최신기술을광범위하게사용하면서수년간프로그래밍과수학을독학했고,현재는전문소프트웨어엔지니어로일하고있다.그는자신의남다른이력이소프트웨어개발에있어서독특하고교과서적인관점에만머무르지않도록해준다고생각한다.현재소방스프링클러시스템의유압계산,설계효용성및적법성검증CAD소프트웨어를개발하는하이드라텍인더스트리(HydratecIndustries)에서일하고있다.

1장리스트,스택,큐
1.1들어가며
1.2연속된자료구조와연결된자료구조
__1.2.1연속된자료구조
__1.2.2연결된자료구조
__1.2.3비교
__1.2.4C스타일배열의제약사항
1.3std::array
__1.3.1연습문제1:동적크기배열구현하기
__1.3.2연습문제2:빠르고범용적인데이터저장컨테이너만들기
1.4std::vector
__1.4.1std::vector-가변크기배열
__1.4.2std::vector할당자
1.5std::forward_list
__1.5.1std::forward_list에서원소삽입과삭제
__1.5.2std::forward_list의기타멤버함수
__1.5.3연습문제3:연결리스트에서remove_if()함수를이용한조건부원소삭제
1.6반복자
__1.6.1연습문제4:다양한반복자에서이동하기
__1.6.2연습문제5:기본적인사용자정의컨테이너만들기
__1.6.3실습문제1:음악재생목록구현하기
1.7std::list
__1.7.1std::list멤버함수
__1.7.2연습문제6:std::list의삽입또는삭제함수사용하기
__1.7.3양방향반복자
__1.7.4반복자무효화
__1.7.5실습문제2:카드게임시뮬레이션
1.8std::deque
__1.8.1덱의구조
1.9컨테이너어댑터
__1.9.1std::stack
__1.9.2std::queue
__1.9.3std::priority_queue
__1.9.4어댑터반복자
1.10벤치마킹
__1.10.1실습문제3:사무실공유프린터의인쇄대기목록시뮬레이션
1.11나가며

2장트리,힙,그래프
2.1들어가며
2.2비선형문제
__2.2.1계층적문제
__2.2.2순환종속성
2.3트리:상하반전된형태
__2.3.1연습문제7:조직도구조만들기
__2.3.2트리순회
__2.3.3연습문제8:레벨순서순회구현하기
2.4다양한트리구조
__2.4.1이진검색트리
__2.4.2트리연산의시간복잡도
__2.4.3연습문제9:BST구현하기
__2.4.4균형트리
__2.4.5N-항트리
__2.4.6실습문제4:파일시스템자료구조만들기
2.5힙
__2.5.1힙연산
__2.5.2연습문제10:중앙값구하기
__2.5.3실습문제5:힙을이용한데이터리스트병합
2.6그래프
__2.6.1인접행렬로그래프표현하기
__2.6.2연습문제11:그래프를구성하고인접행렬로표현하기
__2.6.3인접리스트로그래프표현하기
__2.6.4연습문제12:그래프를구성하고인접리스트로표현하기
2.7나가며

3장해시테이블과블룸필터
3.1들어가며
3.2해시테이블
__3.2.1해싱
__3.2.2연습문제13:정수값을저장하는간단한사전
3.3해시테이블에서충돌
__3.3.1체이닝
__3.3.2연습문제14:체이닝을사용하는해시테이블
__3.3.3열린주소지정
__3.3.4뻐꾸기해싱
__3.3.5연습문제15:뻐꾸기해싱
3.4C++해시테이블
__3.4.1연습문제16:STL에서제공하는해시테이블
__3.4.2실습문제6:긴URL을짧은URL로매핑하기
3.5블룸필터
__3.5.1연습문제17:블룸필터만들기
__3.5.2실습문제7:이메일주소중복검사
3.6나가며

4장분할정복
4.1들어가며
4.2이진검색
__4.2.1연습문제18:이진검색구현및성능평가
__4.2.2실습문제8:예방접종
4.3분할정복이해하기
4.4분할정복을이용한정렬알고리즘
__4.4.1병합정렬
__4.4.2연습문제19:병합정렬
__4.4.3퀵정렬
__4.4.4연습문제20:퀵정렬
__4.4.5실습문제9:부분정렬
__4.4.6선형시간선택
__4.4.7연습문제21:선형시간선택
4.5분할정복기법과C++표준라이브러리함수
4.6맵리듀스:더높은추상화레벨의분할정복기법
__4.6.1맵과리듀스추상화
__4.6.2연습문제22:C++표준라이브러리를이용하여맵과리듀스구현하기
__4.6.3맵리듀스프레임워크를이용한부분통합
__4.6.4연습문제23:맵리듀스를사용하여소수확인하기
__4.6.5실습문제10:맵리듀스를이용하여워드카운트구현하기
4.7나가며

5장그리디알고리즘
5.1들어가며
5.2기본적인그리디알고리즘
__5.2.1최단작업우선스케줄링
__5.2.2연습문제24:최단작업우선스케줄링
5.3배낭문제
__5.3.10-1배낭문제
__5.3.2분할가능배낭문제
__5.3.3연습문제25:분할가능배낭문제
__5.3.4실습문제11:작업스케줄링문제
__5.3.5그리디알고리즘의요구조건
__5.3.6최소신장트리문제
__5.3.7디스조인트-셋자료구조
__5.3.8연습문제26:크루스칼MST알고리즘
5.4그래프컬러링
__5.4.1연습문제27:그리디그래프컬러링
__5.4.2실습문제12:웰시-포웰알고리즘
5.5나가며

6장그래프알고리즘I
6.1들어가며
6.2그래프순회문제
__6.2.1너비우선탐색
__6.2.2연습문제28:BFS구현하기
__6.2.3깊이우선탐색
__6.2.4연습문제29:DFS구현하기
__6.2.5실습문제13:이분그래프판별하기
6.3프림의최소신장트리알고리즘
__6.3.1연습문제30:프림알고리즘구현하기
6.4다익스트라최단경로알고리즘
__6.4.1연습문제31:다익스트라알고리즘구현하기
__6.4.2실습문제14:뉴욕에서최단경로찾기
6.5나가며

7장그래프알고리즘II
7.1들어가며
7.2최단경로문제다시살펴보기
7.3벨만-포드알고리즘
__7.3.1연습문제32:벨만-포드알고리즘구현하기
7.4벨만-포드알고리즘과음수가중치사이클
__7.4.1연습문제33:음수가중치사이클찾기
__7.4.2실습문제15:욕심쟁이로봇
7.5존슨알고리즘
__7.5.1연습문제34:존슨알고리즘구현하기
__7.5.2실습문제16:무작위그래프통계
7.6강한연결요소
__7.6.1방향그래프와무방향그래프에서연결성
7.7코사라주알고리즘
__7.7.1연습문제35:코사라주알고리즘구현하기
__7.7.2실습문제17:미로-순간이동게임
7.8적절한방법선택하기
7.9나가며

8장동적계획법I
8.1들어가며
8.2동적계획법이란?
8.3메모이제이션:하향식접근방법
8.4타뷸레이션:상향식접근방법
8.5부분집합의합문제
__8.5.11단계:동적계획법필요조건분석하기
__8.5.22단계:기저조건과상태정의하기
__8.5.32-(a)단계:전수조사
__8.5.4연습문제36:전수조사방식으로부분집합의합문제풀기
__8.5.52-(b)단계:최적화적용하기-백트래킹
__8.5.6연습문제37:백트래킹을사용하여부분집합의합문제풀기
__8.5.73단계:메모이제이션
__8.5.8연습문제38:메모이제이션을이용하여부분집합의합문제풀기
__8.5.94단계:타뷸레이션
__8.5.10연습문제39:타뷸레이션을이용하여부분집합의합문제풀기
__8.5.11실습문제18:여행경로
8.6문자열과시퀀스에대한동적계획법
__8.6.1최장공통부분시퀀스문제
__8.6.2연습문제40:전수조사방식으로최장공통부분시퀀스문제풀기
__8.6.3최적화첫단계:최적부분구조찾기
__8.6.4실습문제19:메모이제이션을이용하여최장공통부분시퀀스찾기
__8.6.5?하향식에서상향식으로바꾸기:메모이제이션방식을타뷸레이션방식으로바꾸기
__8.6.6실습문제20:타뷸레이션을이용하여최장공통부분시퀀스찾기
8.7실습문제21:멜로디순열
8.8나가며

9장동적계획법II
9.1들어가며
9.2P와NP
9.3부분집합의합문제다시보기
9.4배낭문제
__9.4.10-1배낭문제-부분집합의합문제확장하기
__9.4.2연습문제41:0-1배낭문제
__9.4.3무한개수배낭문제
__9.4.4상태공간축소
__9.4.5연습문제42:무한개수배낭문제
__9.4.6실습문제22:최대이익
9.5그래프와동적계획법
__9.5.1벨만-포드알고리즘다시보기
__9.5.2동적계획법으로최단경로문제다루기
__9.5.3연습문제43:단일시작최단경로(메모이제이션)
__9.5.4모든쌍최단경로
__9.5.5플로이드-워셜알고리즘
__9.5.6연습문제44:플로이드-워셜알고리즘구현하기
__9.5.7실습문제23:도로건설
9.6나가며

부록실습문제풀이

이론과문제풀이를한번에!
C++자료구조에서그래프알고리즘,동적계획법까지!

다양한알고리즘이론을배우고최신C++로구현해보자
C++자료구조부터그리디알고리즘,분할정복알고리즘,그래프알고리즘,동적계획법과같은다양한알고리즘을설명한다.전통적인자료구조와C++STL클래스구현사이의관계를설명해주어진문제에가장적합한자료구조를선택할수있도록도와준다.책의모든코드는C++14로구현되어있다.

44개연습문제와23개실습문제로익히자
다양한알고리즘을설명하기위해단계별문제풀이로직접코딩해보며실용적으로익힐수있게했다.서로다른자료구조가이론적으로는비슷한성능으로동작해야하지만실제컴퓨터에서실행될때는매우큰차이가발생할수있다는것을연습문제풀이로보여준다.또한,익힌내용은실습문제로한번더정리할수있게했다.코딩테스트를준비하는취업준비생과최신C++문법으로알고리즘을새로공부하려는사람들에게추천한다.

자주출제되는주요알고리즘위주로배우자
코딩테스트도전략이필요하다.다양한알고리즘이있지만,그중코딩테스트에자주출제되는주요알고리즘으로구성했다.분할정복,그래프탐색,최단경로,동적계획법등많이출제되는알고리즘에집중하자.