그동안 자료구조 수업에 아쉬움을 채워줄 신간 교재!!

★ 자료구조의 구현을 난이도에 따라서 여러 방법으로 소개
- 간단한 방법과 조금 복잡하지만 효율적인 방법을 차례로 기술
★ 게임과 인공지능에 적용되는 자료구조 예제 포함
★ 시각적 출력을 이용한 학습 흥미 부여
★ 실용적인 데이터 사용

이 책의 다른 점

저자가 이 책을 쓰려고 마음 먹은 이유는, 자료 구조를 배우는 과정에서 자주 겪는 단점들을 줄이면서 공부할 수 있는 교재를 만드는 것이었다. 이를 위해서 이 책은 기존의다른 자료 구조 교재와 다른 점이 많다. 이 책의 성격을 확실히 설명하는 것이 독자들이 더욱 효과적으로 이 교재를 보는 방법일 것이다.

*한 종류의 자료 구조의 구현을 난이도에 따라서 여러 방법으로 소개하였다 : 각각의 자료구조를 구현함에 있어서 간단한 방법과, 조금은 더 복잡하지만 효율적인 방법을 차례로 기술하려고 하였다. 이 교재를 처음부터 끝까지 빠짐없이 모두 공부하는 것보다, 자신이 이해되는 수준에서 학습의 깊이를 설정하고, 여러 번 교재를 보면서 조금씩 자신의 지식의 깊이를 심화할 수 있도록 하였다. 자신의 프로그래밍 실력에 적합한 버전부터 하나씩 차례로 공부하자.

*게임과 인공 지능에 적용되는 자료 구조를 다룬다 : 모든 공부는 흥미 유발이 중요하다.
지금 배우는 각 자료 구조가 어떻게 인공 지능 분야와 게임 프로그래밍에 사용될 수있는지 소개함으로써 동기 부여에 도움이 되도록 하였다.

*시각적 출력을 이용한 학습 흥미 부여 : 그래픽 결과를 출력하는 프로그램을 작성해서흥미를 유발한다. C 언어 프로그래밍은 대부분 콘솔(텍스트 모드의 입출력) 화면에서 글자 출력으로 시작한다. 이 책에서는 오픈프레임웍스(openFrameworks)라는 라이브러리를 이용해서 다양한 그래픽 출력을 함으로써, 각 자료 구조가 실제 문제에 어떻게 사용될 수 있는지를 보이려고 노력하였다.

*실용적인 데이터를 사용한다 : 대부분의 교재에서는 10~100여개 정도의 데이터를 자료 구조의 테스트 데이터로 사용한다. 다양한 자료 구조들은 대용량의 데이터를 사용할 때 성능의 차이가 명확해진다. 수 십, 수 백 개 정도의 소량의 데이터들을 다룰때는 각 자료 구조들의 효율성이 실감나지 않는다. 이미 하드웨어가 엄청나게 빠르기 때문이다. 그래서 이 교재에서는 대량의 데이터를 실습 데이터로 사용하고, 이 데이터는 인터넷에 업로드해서 다운로드 받아서 사용할 수 있도록 하였다.

이외에 세부적인 특징들은 다음과 같다.

* C 언어 중에서 자료 구조 공부에 필요한 부분은 별도로 정리하였다 : 배열, 구조체, 파일 입출력, 포인터 등의 개념은 C 언어를 이용한 자료 구조 이해를 위해서 필수적이다. 각 내용들이 필요할 때 적절한 곳에 이 항목들을 다시 소개한다. 그렇지만 이 교재를 보기 위해서는 각자 C 언어의 선행 학습은 꼭 필요하다.

*소스 코드는 교재의 좌우 지면 여백에 설명을 추가함으로써 독자들이 쉽게 코드를 이해할 수 있도록 편집하였다.

PART I : 본격적인 자료 구조 공부에 앞서

CHAPTER 1 프로그래밍 기초와 소프트웨어 공학 3
1.1 소프트웨어 공학 5
1.2 소프트웨어 개발 주기 6
1.3 문제 해결을 위한 프로그래밍의 절차 7
1.4 일반적인 코딩 팁 10
1.5 이 책에서 사용하는 코딩 규칙 11
1.6 디버깅하는 방법 13

CHAPTER 2 자료 구조와 알고리즘의 기초 15
2.1 자료 구조란? 17
2.2 일상 생활에서 사용하는 자료 구조들의 예 19
2.3 알고리즘이란? 22
2.3.1 알고리즘 효율성 분석 #1 23
2.3.2 알고리즘 효율성 분석 #2 29
2.3.3 BIG-O 표기법 34
2.4 추상 데이터 타입(Abstract Data Type: ADT) 36
2.5 기본 자료형 39
연습문제 40

CHAPTER 3 Visual Studio와 openFrameworks 기초 43
3.1 openFrameworks와 Visual Studio 설치 46
3.1.1 openFrameworks 설치 47
3.1.2 Visual Studio Community 2017 버전 설치 48
3.1.3 Visual Studio에서의 C 언어를 이용한 콘솔 프로그래밍 51
3.2 오픈프레임웍스 프로그래밍 시작 64
3.2.1 오픈프레임웍스 라이브러리의 폴더 구조 64
3.2.2 오픈프레임웍스 empty 프로그램 제작 66
3.2.3 오픈프레임웍스 소스 코드 구조 72
3.2.4 오픈프레임웍스 텍스트 모드 프로그램 제작 73
3.2.5 오픈프레임웍스 그래픽 모드 프로그램 제작 76
3.3 파일 분할 및 헤더 파일 구성 방법 #1 81
3.3.1 오픈프레임웍스 공 움직이기 82
3.3.2 오픈프레임웍스 라켓으로 공 반사하기 87
3.3.3 오픈프레임웍스 big-O 그래프로 비교해보기 90
3.4 헤더 파일에 적는 내용 #2 92
3.4.1 헤더 파일(간단한 경우) 92
3.4.2 헤더 파일(조금 더 복잡한 경우) 94

PART II : 자료 구조 기초(선형 자료 구조)

CHAPTER 4 배열(ARRAY) 99
4.1 1차원 배열 101
4.1.1 1차원 배열 정의 101
4.1.2 1차원 배열 사용 103
4.1.3 오픈프레임웍스 1차원 배열의 응용: 돗수 분포표/돗수 분포 그래프 109
4.2 2차원 배열 112
4.2.1 2차원 배열 정의 113
4.2.2 2차원 배열 사용: (기본)행렬 연산 구현 114
4.2.3 오픈프레임웍스 벽돌 깨기 게임에 벽돌 배치하기 121
4.2.4 오픈프레임웍스 3차원 배열의 응용: 숫자 인식 프로그램 125
4.2.5 openFrameworks 사용을 위한 객체 지향 프로그래밍 소개 134
4.2.6 오픈프레임웍스 2차원 배열 \u003d\u003d 이미지(image) 137
4.3 구조체(struct) 140
4.3.1 구조체 변수와 일반 변수의 같은 점, 다른 점 142
4.3.2 함수의 파라미터로 사용되는 구조체 144
4.3.3 typedef 147
4.3.4 심화 2차원 행렬 연산 구현 149
4.4 희소 행렬(稀少, sparse matrix) 154
4.4.1 (기본 #1) 희소 행렬 구현 155
4.4.2 (기본 #2) 희소 행렬 구현 157
4.4.3 심화 희소 행렬 구현 162
4.5 파일 입출력 170
4.5.1 표준 입·출력 정리 171
4.5.2 텍스트 파일 입·출력 함수 173
4.5.3 새 파일 만들어서 문자 쓰기 174
4.5.4 기존 파일 읽기 176
4.5.5 Visual Stduio에서 파일 사용하기 177
4.6 심화 영한 단어장 180
연습문제 184

CHAPTER 5 배열 리스트(array list) 187
5.1 배열 리스트 의사 코드 190
5.2 배열 리스트 구현 191
5.3 보다 실용적인 리스트 구현 방법 198
5.4 배열 리스트 관련 알고리즘 보충 설명 205
5.4.1 검색 205
5.4.2 추가 211
5.4.3 삭제 212
5.4.4 정렬 213
5.5 오픈프레임웍스 벽돌 깨기 게임 총알 기능 217

CHAPTER 6 연결 리스트(linked list) 225
6.1 연결 리스트 기본 228
6.2 C 언어에서의 포인터 231
6.2.1 포인터 고찰 232
6.2.2 포인터 변수의 연산 239
6.2.3 포인터 변수의 장점 243
6.2.4 배열과 포인터의 차이점 244
6.2.5 포인터와 문자열 246
6.2.6 포인터를 이용한 동적 메모리 할당 249
6.2.7 포인터 배열 254
6.2.8 이중 포인터 255
6.3 단일 연결 리스트(singly linked list) ADT 256
6.4 단일 연결 리스트 구현 256
6.5 배열 리스트와 연결 리스트의 비교 267
6.6 오픈프레임웍스 파티클 효과 구현 267
6.7 원형(환형) 연결 리스트(circular linked list) 273
6.8 이중 연결 리스트(doubly linked lists) 279
연습문제 284

CHAPTER 7 스택(stacks) 287
7.1 1차원 배열을 이용한 스택 구현 294
7.2 응용 괄호 매칭 검사 297
7.3 응용 후위 표기식(postfix) 계산 301
7.3.1 중위 표기법의 후위 표기법 변경 코드 303
7.3.2 후위 표기법 계산 코드 305
7.4 응용 미로 탈출 308
7.4.1 스택을 이용한 구현 308
7.4.2 재귀함수(recursive function) 309
7.4.3 오픈프레임웍스 미로 탈출: 스택 이용 312
7.4.4 오픈프레임웍스 미로 탈출: 재귀함수 이용 316
7.5 오픈프레임웍스 재귀함수의 응용 319
7.5.1 프랙탈 319
7.5.2 몬드리안 그림 320
연습문제 322

CHAPTER 8 큐(queues) 325
8.1 1차원 배열을 이용한 큐 구현 328
8.2 1차원 배열을 이용한 원형 큐 구현 332
8.3 1차원 배열을 이용한 원형 큐 구현(배열의 모든 원소 사용 가능) 336
8.4 심화 큐의 응용 338
8.4.1 생산자-소비자 문제(Producer and Consumer Problem) 338
8.4.2 임계 영역(critical section) 339
8.4.3 멀티 쓰레드 프로그래밍 342
연습문제 346

PART III : 자료 구조 중급(비 선형 자료 구조)

CHAPTER 9 트리(trees) 349
9.1 트리 기초 352
9.1.1 트리에서 사용하는 용어 정리 353
9.1.2 트리의 종류 354
9.2 이진 트리(binary tree) 357
9.2.1 배열을 이용한 이진 트리 구현 360
9.2.2 배열을 이용한 결정 트리(decision tree) 366
9.2.3 포인터를 이용한 이진 트리 구현 370
9.2.4 포인터를 이용한 이진 트리 구현(추가) 374
9.2.5 이진 트리 순회(traversal) 376
9.2.6 이진 트리와 관련된 다양한 연산 384
9.3 이진 탐색 트리(binary search tree) 387
9.3.1 검색 389
9.3.2 추가 391
9.3.3 삭제 393
9.3.4 테스트 결과 396
9.4 심화 게임 트리(game tree) 398
9.4.1 Min-Max Tree 400
9.4.2 정적 형세 판단(static evaluation) 403
9.4.3 Min-Max 트리 구현 409
9.4.4 오픈프레임웍스 틱택토 구현 410
연습문제 416

CHAPTER 10 그래프(graphs) 417
10.1 그래프 기초 420
10.2 그래프 구현 423
10.2.1 인접 행렬을 이용한 구현 423
10.2.2 인접 리스트를 이용한 구현 435
10.3 응용 지하철 노선 데이터 443
10.4 그래프 탐색 451
10.4.1 깊이 우선 탐색 452
10.4.2 너비 우선 탐색 453
10.4.3 그래프 탐색 구현 455
10.5 연결 성분(connected component) 459
10.6 신장 트리(spanning trees) 463
10.7 최소 신장 트리(minimum spanning trees: MST) 466
10.7.1 Kruskal의 MST 알고리즘 개괄 466
10.7.2 Prim의 MST 알고리즘 478
10.8 최단 경로(Shortest Path) 478
10.8.1 데익스트라(Dijkstra) 알고리즘 개요 479
10.8.2 데익스트라 알고리즘 구현 485
10.8.3 A* 알고리즘 489
10.8.4 Floyd 알고리즘 491
연습문제 492

PART IV : 자료 구조 고급
CHAPTER 11 우선 순위 큐(priority queue) 495
11.1 정렬 알고리즘 497
11.1.1 선택 정렬(selection sorting) 498
11.1.2 병합 정렬(merge sorting) 500
11.2 우선 순위 큐 505
11.2.1 배열을 이용한 우선 순위 큐 506
11.2.2 연결 리스트를 이용한 우선 순위 큐 506
11.3 힙(heap) 507
11.3.1 힙의 연산 509
11.3.2 힙의 구현 510
연습문제 516

CHAPTER 12 해싱(hashing) 517
12.1 해싱의 기본 519
12.2 해시 함수(hash function)와 해시 테이블(hash table) 521
12.2.1 간단한 해시 함수: 자리 수 선택 522
12.2.2 간단한 해싱 함수 구현 523
12.3 충돌 해결책 525
12.3.1 오픈 어드레싱(open addressing) 525
12.3.2 체이닝(chaining) 526
12.3.3 체이닝을 이용한 해싱 구현 527
연습문제 534
INDEX 535