홈앤서비스 SK BROADBAND

자료구조+알고리즘의 개념부터 실습까지
포기 없이 즐겁게 배우자!

자료구조와 알고리즘은 IT 기업의 면접과 코딩 테스트 통과를 위한 필수 역량이다. 알고리즘을 배워두면 단순히 취업뿐 아니라 더 좋은 개발자가 되는 데 큰 도움이 된다. 하지만 자료구조와 알고리즘은 배우기 어려우며 심지어 재미도 없다 보니 많은 개발자가 중도에 학습을 포기한다. 『이것이 자료구조+알고리즘이다』는 독자가 마지막 페이지까지 읽도록 하는 것에 목표를 두었다.

처음 배우는 사람의 눈높이에 맞춰 리스트부터 백트래킹까지 자주 사용되는 자료구조와 알고리즘 개념을 위트 넘치는 이야기로 쉽게 설명한다. 보기만 해도 헉 소리가 나는 복잡한 수식은 최소화하고 이해에 꼭 필요한 수식만 담았다. 또한 작동 원리를 단번에 이해할 수 있게 도와주는 다양한 그림과 바로 실행하고 확인할 수 있는 108개 소스 코드를 예제로 제공해 알고리즘의 얼개를 완벽히 이해할 수 있도록 구성했다. 『이것이 자료구조+알고리즘이다』와 함께 자료구조와 알고리즘의 주요 개념을 포기 없이 끝까지 배워보자!

__지은이의 말
__이 책의 구성
__학습 로드맵

Chapter 00 알아두면 쓸 데 있는 자료구조와 알고리즘
_0.1 자료구조
_0.2 알고리즘
_0.3 C 언어로 메모리를 다루는 방법
__0.3.1 포인터 복습
__0.3.2 구조체 복습
__0.3.3 메모리 레이아웃 복습
__0.3.4 스택에서 데이터를 다루는 방법
__0.3.5 힙에서 데이터를 다루는 방법

Part 01 자료구조
Chapter 01 리스트
_1.1 리스트 ADT
__1.1.1 리스트의 개념
__1.1.2 리스트와 배열 비교
_1.2 링크드 리스트
__1.2.1 링크드 리스트의 노드 표현
__1.2.2 링크드 리스트의 주요 연산
___Vitamin Quiz 1-1
__1.2.3 링크드 리스트 예제 프로그램
__1.2.4 링크드 리스트의 장단점
___Vitamin Quiz 1-2
_1.3 더블 링크드 리스트
__1.3.1 더블 링크드 리스트의 주요 연산
__1.3.2 더블 링크드 리스트 예제 프로그램
___Vitamin Quiz 1-3
_1.4 환형 링크드 리스트
__1.4.1 환형 더블 링크드 리스트의 주요 연산
__1.4.2 환형 더블 링크드 리스트 예제 프로그램
_연습문제

Chapter 02 스택
_2.1 스택 ADT
__2.1.1 스택의 개념
___Vitamin Quiz 2-1
__2.1.2 스택의 핵심 기능: 삽입과 제거 연산
_2.2 배열로 구현하는 스택
__2.2.1 배열 기반 스택과 스택의 노드 표현
__2.2.2 배열 기반 스택의 기본 연산
__2.2.3 배열 기반 스택 예제 프로그램
___Vitamin Quiz 2-2
_2.3 링크드 리스트로 구현하는 스택
__2.3.1 링크드 리스트 기반 스택과 스택의 노드 표현
__2.3.2 링크드 리스트 기반 스택의 기본 연산
__2.3.3 링크드 리스트 기반 스택 예제 프로그램
_2.4 스택의 응용: 사칙 연산 계산기
__2.4.1 수식의 중위 표기법과 후위 표기법
__2.4.2 후위 표기식을 계산하는 알고리즘
__2.4.3 중위 표기식을 후위 표기식으로 바꾸는 알고리즘
__2.4.4 사칙 연산 계산기 예제 프로그램
_연습문제

Chapter 03 큐
_3.1 큐 ADT
__3.1.1 큐의 개념
__3.1.2 큐 ADT의 핵심 기능: 삽입과 제거 연산
_3.2 순환 큐
__3.2.1 공백 상태와 포화 상태
__3.2.2 순환 큐의 기본 연산
__3.2.3 순환 큐 예제 프로그램
_3.3 링크드 큐
__3.3.1 링크드 큐의 기본 연산
__3.3.2 링크드 큐 예제 프로그램
_연습문제

Chapter 04 트리
_4.1 트리 ADT
__4.1.1 트리의 개념
__4.1.2 트리의 구성 요소
__4.1.3 트리 표현 방법
__4.1.4 노드 표현 방법
__4.1.5 트리의 기본 연산
__4.1.6 트리 예제 프로그램
___Vitamin Quiz 4-1
_4.2 이진 트리
__4.2.1 이진 트리의 종류
__4.2.2 이진 트리의 순회
__4.2.3 이진 트리의 기본 연산
__4.2.4 이진 트리 예제 프로그램
_4.3 수식 트리
__4.3.1 수식 트리 구축 방법
__4.3.2 수식 트리의 구현
__4.3.3 수식 트리 예제 프로그램
_4.4 분리 집합
__4.4.1 분리 집합 표현
__4.4.2 분리 집합의 기본 연산
__4.4.3 분리 집합 예제 프로그램
_연습문제

Part 02 알고리즘
Chapter 05 정렬
_5.1 정렬 알고리즘의 개요
_5.2 버블 정렬
__5.2.1 버블 정렬의 성능 측정
__5.2.2. 버블 정렬 예제 프로그램
___Vitamin Quiz 5-1
_5.3 삽입 정렬
__5.3.1 삽입 정렬의 성능 측정
__5.3.2 삽입 정렬 예제 프로그램
_5.4 퀵 정렬
__5.4.1 퀵 정렬 사용 전 해결해야 하는 2가지 문제
__5.4.2 퀵 정렬 예제 프로그램
__5.4.3 퀵 정렬의 성능 측정
_5.5 C 언어 표준 라이브러리의 퀵 정렬 함수: qsort( )
__5.5.1 qsort( ) 함수 예제 프로그램
___Vitamin Quiz 5-2
__5.5.2 qsort( ) 응용 문제
_연습문제

Chapter 06 탐색
_6.1 탐색 알고리즘의 개요
_6.2 순차 탐색
__6.2.1 전진 이동법
___Vitamin Quiz 6-1
__6.2.2 전위법
___Vitamin Quiz 6-2
__6.2.3 계수법
___Vitamin Quiz 6-3
_6.3 이진 탐색
__6.3.1 이진 탐색의 성능 측정
__6.3.2 이진 탐색의 구현
__6.3.3 이진 탐색 예제 프로그램: 두 번째 최종 시험 문제
__6.3.4 C 언어 표준 라이브러리의 이진 탐색 함수: bsearch( )
__6.3.5 bsearch( ) 함수 예제 프로그램
_6.4 이진 탐색 트리
__6.4.1 이진 탐색 트리 표현
__6.4.2 이진 탐색 트리의 기본 연산
__6.4.3 이진 탐색 트리 예제 프로그램
__6.4.4 이진 탐색 트리의 문제점
_6.5 레드 블랙 트리
__6.5.1 레드 블랙 트리의 구현 규칙
__6.5.2 레드 블랙 트리의 기본 연산
__6.5.3 레드 블랙 트리 예제 프로그램
_연습문제

Chapter 07 우선순위 큐와 힙
_7.1 우선순위 큐
__7.1.1 우선순위 큐의 삽입/제거 연산
__7.1.2 우선순위 큐의 구현
_7.2 힙
__7.2.1 힙의 삽입 연산
__7.2.2 힙의 최솟값 삭제 연산
__7.2.3 힙의 구현
__7.2.4 힙 예제 프로그램
_7.3 힙 기반 우선순위 큐의 구현
_연습문제

Chapter 08 해시 테이블
_8.1 해시 테이블의 개요
__8.1.1 해시
__8.1.2 해시 테이블
_8.2 해시 함수
__8.2.1 나눗셈법
__8.2.2 자릿수 접기
__8.2.3 해시 함수의 한계: 충돌
_8.3 충돌 해결 기법
__8.3.1 체이닝
__8.3.2 개방 주소법
_연습문제

Chapter 09 그래프
_9.1 그래프의 개요
__9.1.1 그래프의 탄생 배경: 오일러의 문제 해결 도구
__9.1.2 그래프의 정의
___Vitamin Quiz 9-1
_9.2 그래프 표현 방법
__9.2.1 인접 행렬
__9.2.2 인접 리스트
___Vitamin Quiz 9-2
_9.3 그래프 순회 기법
__9.3.1 깊이 우선 탐색
__9.3.2 너비 우선 탐색
__9.3.3 그래프 순회 예제 프로그램
_9.4 위상 정렬
__9.4.1 위상 정렬의 동작 방식
__9.4.2 위상 정렬 예제 프로그램
_9.5 최소 신장 트리
__9.5.1 프림 알고리즘
__9.5.2 크루스칼 알고리즘
__9.5.3 최소 신장 트리 예제 프로그램
_9.6 최단 경로 탐색: 데이크스트라 알고리즘
__9.6.1 데이크스트라 알고리즘의 개념
__9.6.2 데이크스트라 알고리즘 예제 프로그램
_연습문제

Chapter 10 문자열 탐색
_10.1 문자열 탐색 알고리즘의 개요
_10.2 고지식한 탐색 알고리즘
__10.2.1 고지식한 탐색의 동작 방식
__10.2.2 고지식한 탐색 알고리즘 예제 프로그램
_10.3 카프-라빈 알고리즘
__10.3.1 카프-라빈 알고리즘의 동작 방식
__10.3.2 카프-라빈 알고리즘 예제 프로그램
_10.4 KMP 알고리즘
__10.4.1 KMP 알고리즘의 동작 방식
__10.4.2 경계 정보 사전 계산 방법
__10.4.3 KMP 알고리즘 예제 프로그램
_10.5 보이어-무어 알고리즘
__10.5.1 나쁜 문자 이동
__10.5.2 착한 접미부 이동
__10.5.3 보이어-무어 알고리즘의 전처리 과정
__10.5.4 보이어-무어 알고리즘 예제 프로그램
_연습문제

Part 03 알고리즘 설계 기법
Chapter 11 알고리즘 성능 분석
_11.1 알고리즘 성능 측정 기준과 수행 시간
__11.1.1 알고리즘 성능 측정 기준
__11.1.2 알고리즘 수행 시간 분석
_11.2 점근 표기법
__11.2.1 O 표기법
__11.2.2 Ω 표기법
__11.2.3 Θ 표기법
_11.3 재귀 알고리즘 성능 분석
__11.3.1 재귀 방정식과 재귀 알고리즘
__11.3.2 퀵 정렬의 성능 분석
__11.3.3 마스터 정리
_연습문제

Chapter 12 분할 정복
_12.1 분할 정복 기법의 개요
__12.1.1 분할 정복 전술의 탄생 배경: 아우스터리츠 전투
__12.1.2 분할 정복 알고리즘의 개념
_12.2 병합 정렬
__12.2.1 병합 정렬 동작 방식
__12.2.2 병합 정렬 알고리즘의 구현
_12.3 거듭 제곱 계산
__12.3.1 거듭 제곱 계산법
__12.3.2 거듭 제곱 계산 알고리즘의 구현
_12.4 분할 정복 기반 피보나치 수 구하기
__12.4.1 피보나치 수를 구하는 방법
__12.4.2 분할 정복으로 피보나치 수를 구하는 방법
__12.4.3 분할 정복 기반 피보나치 수 구하기 알고리즘의 구현
연습문제

Chapter 13 동적 계획법
_13.1 동적 계획법의 개요
__13.1.1 동적 계획법의 탄생 배경
__13.1.2 동적 계획법의 개념
_13.2 동적 계획법 기반 피보나치 수 구하기
__13.2.1 동적 계획법으로 피보나치 수를 구하는 방법
__13.2.2 동적 계획법 기반 피보나치 수 구하기 알고리즘의 구현
_13.3 최장 공통 부분 수열
__13.3.1 LCS 알고리즘
__13.3.2 동적 계획법 기반 LCS 알고리즘의 구현
_연습문제

Chapter 14 탐욕 알고리즘
_14.1 탐욕 알고리즘의 개요
_14.2 거스름돈 줄이기 문제
__14.2.1 거스름돈 계산 예제 프로그램
__14.2.2 탐욕 알고리즘의 중요한 속성
_14.3 크루스칼 알고리즘 다시 보기
_14.4 데이크스트라 알고리즘 다시 보기
_14.5 허프만 코딩
__14.5.1 고정 길이 코드와 접두어 코드
__14.5.2 허프만 트리 구축
__14.5.3 데이터 압축
__14.5.4 데이터 압축 해제
__14.5.5 허프만 코딩 예제 프로그램
_연습문제

Chapter 15 백트래킹
_15.1 백트래킹의 개요
__15.1.1 백트래킹의 사례: 테세우스 이야기
__15.1.2 백트래킹의 개념
_15.2 미로 탈출로 찾기
__15.2.1 재귀 호출 기반 백트래킹
__15.2.2 미로 탈출 알고리즘의 구현
__15.2.3 미로 탈출 알고리즘 예제 프로그램
_15.3 8개의 퀸 문제
__15.3.1 8개의 퀸이 만드는 해공간과 백트래킹
__15.3.2 N개의 퀸 문제 풀이 알고리즘의 구현
__15.3.3 N개의 퀸 문제 풀이 예제 프로그램
_연습문제

__찾아보기