코딩 테스트 준비 및 최신?C++?문법으로 알고리즘을 학습하자!
C++?자료 구조부터 그리디 알고리즘,?분할 정복 알고리즘,?그래프 알고리즘,?동적 계획법과 같은 다양한 알고리즘을 설명한다.?또한,?전통적인 자료 구조와?C++ STL?클래스 구현 사이의 관계를 설명해 주어진 문제에 가장 적합한 자료 구조를 선택할 수 있도록 도와준다.?이론을 익힌 후?44개 연습 문제와?23개 실습 문제로 직접 코딩해보며 체계적으로 학습할 수 있게 구성되어 있다.?코딩 테스트를 준비하는 취업 준비생과 최신?C++?문법으로 알고리즘을 새로 공부하려는 사람들에게 추천한다.

인도 아마다바드(Ahmedabad)에 있는 니르마 대학(Nirma University)에서 컴퓨터 공학으로 학사 학위를 받았다. 졸업 후에는 금융 업계에 입사했고, 최신 C++ 응용 프로그램을 이용한 초저지연(ultra-low latency) 거래 시스템을 개발했다. 최근 3년 동안은 C++를 사용한 거래 인프라(trading infrastructure) 설계를 맡고 있다.

1장 리스트,?스택,?큐
1.1?들어가며
1.2?연속된 자료 구조와 연결된 자료 구조
__1.2.1?연속된 자료 구조
__1.2.2?연결된 자료 구조
__1.2.3?비교
__1.2.4 C?스타일 배열의 제약 사항
1.3 std::array
__1.3.1?연습 문제?1:?동적 크기 배열 구현하기
__1.3.2?연습 문제?2:?빠르고 범용적인 데이터 저장 컨테이너 만들기
1.4 std::vector
__1.4.1 std::vector -?가변 크기 배열
__1.4.2 std::vector?할당자
1.5 std::forward_list
__1.5.1 std::forward_list에서 원소 삽입과 삭제
__1.5.2 std::forward_list의 기타 멤버 함수
__1.5.3?연습 문제?3:?연결 리스트에서?remove_if()?함수를 이용한 조건부 원소 삭제
1.6?반복자
__1.6.1?연습 문제?4:?다양한 반복자에서 이동하기
__1.6.2?연습 문제?5:?기본적인 사용자 정의 컨테이너 만들기
__1.6.3?실습 문제?1:?음악 재생 목록 구현하기
1.7 std::list
__1.7.1 std::list?멤버 함수
__1.7.2?연습 문제?6: std::list의 삽입 또는 삭제 함수 사용하기
__1.7.3?양방향 반복자
__1.7.4?반복자 무효화
__1.7.5?실습 문제?2:?카드 게임 시뮬레이션
1.8 std::deque
__1.8.1?덱의 구조
1.9?컨테이너 어댑터
__1.9.1 std::stack
__1.9.2 std::queue
__1.9.3 std::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.5 N-항 트리
__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.4 C++?해시 테이블
__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.1 0-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.1 1단계:?동적 계획법 필요조건 분석하기
__8.5.2 2단계:?기저 조건과 상태 정의하기
__8.5.3 2-(a)단계:?전수 조사
__8.5.4?연습 문제?36:?전수 조사 방식으로 부분집합의 합 문제 풀기
__8.5.5 2-(b)단계:?최적화 적용하기?-?백트래킹
__8.5.6?연습 문제?37:?백트래킹을 사용하여 부분집합의 합 문제 풀기
__8.5.7 3단계:?메모이제이션
__8.5.8?연습 문제?38:?메모이제이션을 이용하여 부분집합의 합 문제 풀기
__8.5.9 4단계:?타뷸레이션
__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.2 P와?NP
9.3?부분집합의 합 문제 다시 보기
9.4?배낭 문제
__9.4.1 0-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?나가며
?
부록 실습 문제 풀이