길벗·이지톡

도서 IT 전문서 프로그래밍/오픈소스
67개 문제 풀이로 익히자! 코딩 테스트를 위한 자료 구조와 알고리즘 with C++
정 가
32,000원
I S B N
9791165213794
출 간
2020-12-08
분 량
552쪽
지 은 이
존캐리, 셰리안도시, 파야스라잔
난 이 도
중급,고급
옮 긴 이
황선규
부 록
예제 소스 코드

67개 문제 풀이로 익히는 C++ 자료 구조와 알고리즘!

코딩 테스트 준비 및 최신 C++ 문법으로 알고리즘을 학습하자!

 

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

 

 

 

목차

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 PNP

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 나가며

 

 

 

부록 실습 문제 풀이

더보기접기

저자

ㆍ지은이 존캐리, 셰리안도시, 파야스라잔

지은이 소개

존 캐리(John Carey)

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

 

셰리안 도시(Shreyans Doshi)

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

 

파야스 라잔(Payas Rajan)

 

 

NIT 알라하바드(NIT Allahabad)에서 컴퓨터 과학 기술 학사 학위를 받았다. 이후 삼성리서치인도연구소(Samsung Research India)에 입사하여 타이젠(Tizen) 멀티미디어 프레임워크 개발에 참여했다. 현재는 캘리포니아 대학 리버사이드(University of California Riverside)에서 지리 공간 데이터베이스 및 경로 계획 알고리즘을 전공하는 박사 과정을 밟으면서 교육 및 연구 조교로 일하고 있으며, 10년 동안 C++를 사용하여 응용 프로그램을 개발해왔다.

ㆍ옮긴이 황선규

옮긴이 소개

2006년 한양대학교에서 영상 처리 전공으로 박사 학위를 받았으며, 이후 뉴질랜드 캔터베리 대학교와 한양대학교에서 박사후과정(Post-Doc)과 연구 교수로 재직하였다. 2009LG전자 MC연구소에 입사하여 전략 스마트폰 카메라 기능 개발과 안드로이드 카메라 프레임워크 업무를 담당하였다. 2016년부터 패스트캠퍼스에서 직장인을 대상으로 하는 OpenCV 강의를 진행하고 있고, 기업체와 대학에서 특강도 진행하고 있다. 易地思之가 좌우명이고, ‘知之爲知之 不知爲不知 是知也글귀를 좋아한다.

https://sunkyoo.github.io/

저서

저서 《영상 처리 프로그래밍 by Visual C++》,《Visual C++ 영상 처리 프로그래밍

역서 《OpenCV 제대로 배우기


연관 프로그램

아래 프로그램은 길벗출판사가 제공하는 것이 아닙니다.
무료로 사용할 수 있는 정보를 안내해 드리니, 지원이 필요하면 해당 프로그렘 제작사로 문의해 주세요.