출판사:

연두에디션

저   자:

정기철

발행일:

2018-07-15

가   격:

27,000원

페이지:

542 페이지

ISBN:

979-11-88831-09-8

도   수 :

2도

도서자료

• 교수용 도서 자료실
• 학생용 도서 자료실
• 강의자료
• 교수용 도서자료

• 교수용 도서자료2

교재내용

*한 종류의 자료 구조의 구현을 난이도에 따라서 여러 방법으로 소개하였다 : 각각의 자료구조를 구현함에 있어서 간단한 방법과, 조금은 더 복잡하지만 효율적인 방법을 차례로 기술하려고 하였다.

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

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

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

목차

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 오픈프레임웍스 시작 #1: empty 프로그램 제작 66
3.2.3 오픈프레임웍스 소스 코드 구조 72
3.2.4 오픈프레임웍스 시작 #2: 텍스트 모드 프로그램 제작 73
3.2.5 오픈프레임웍스 시작 #3: 그래픽 모드 프로그램 제작 76
3.3 파일 분할 및 헤더 파일 구성 방법 #1 81
3.3.1 오픈프레임웍스 실전 #1: 공 움직이기 82
3.3.2 오픈프레임웍스 실전 #2: 라켓으로 공 반사하기 87
3.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 openFramework 사용을 위한 객체 지향 프로그래밍 소개 134
4.2.6 오픈프레임웍스 2차원 배열 == 이미지(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 파일 입출력 171
4.5.1 표준 입·출력 정리 172
4.5.2 텍스트 파일 입·출력 함수 173
4.5.3 새 파일 만들어서 문자 쓰기 174
4.5.4 기존 파일 읽기 176
4.5.5 Visual Stduio에서 파일 사용하기 178
4.6 응용 영한 단어장 181
연습문제 185

CHAPTER 5 배열 리스트(array list) 187
5.1 배열 리스트 의사 코드 190
5.2 배열 리스트 구현 192
5.3 보다 실용적인 리스트 구현 방법 198
5.4 배열 리스트 관련 알고리즘 보충 설명 205
5.4.1 검색(search) 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 배열 리스트와 연결 리스트의 비교 268
6.6 오픈프레임웍스 파티클 효과 구현 268
6.7 원형(환형) 연결 리스트(circular linked list) 274
6.8 이중 연결 리스트(doubly linked lists) 280
연습문제 286

CHAPTER 7 스택(Stacks) 289
7.1 1차원 배열을 이용한 스택 구현 296
7.2 응용 괄호 매칭 검사 299
7.3 응용 후위 표기식(postfix) 계산 303
7.3.1 중위 표기법의 후위 표기법 변경 코드 306
7.3.2 후위 표기법 계산 코드 308
7.4 응용 미로 탈출 310
7.4.1 스택을 이용한 구현 310
7.4.2 재귀함수(recursive function) 311
7.4.3 오픈프레임웍스 미로 탈출: 스택 이용 315
7.4.4 오픈프레임웍스 미로 탈출: 재귀함수 이용 318
7.5 오픈프레임웍스 재귀함수의 응용 321
7.5.1 프랙탈 321
7.5.2 몬드리안 그림 322
연습문제 324

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 포인터를 이용한 이진 트리 구현(추가) 375
9.2.5 이진 트리 순회(traversal) 376
9.2.6 이진 트리와 관련된 다양한 연산 384
9.3 이진 탐색 트리(binary search trees) 387
9.3.1 검색 389
9.3.2 추가 392
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) 404
9.4.3 Min-Max 트리 구현 409
9.4.4 오픈프레임웍스 틱택토 구현 411
연습문제 418

CHAPTER 10 그래프(graphs) 421
10.1 그래프 기초 424
10.2 그래프 구현 427
10.2.1 인접 행렬을 이용한 구현 427
10.3 심화 인접 행렬을 이용한 그래프 구현 433
10.3.1 인접 리스트를 이용한 구현 439
10.4 응용 지하철 노선 데이터 447
10.5 그래프 탐색 455
10.5.1 깊이 우선 탐색 456
10.5.2 너비 우선 탐색 457
10.5.3 그래프 탐색 구현 459
10.5.4 인접 행렬 459
10.5.5 인접 리스트 461
10.6 연결 성분(connected component) 463
10.7 신장 트리(spanning trees) 467
10.8 최소 신장 트리(minimum spanning trees: MST) 470
10.8.1 Kruskal의 MST 알고리즘 개괄 470
10.8.2 union-find 알고리즘 473
10.8.3 Kruskal의 MST 알고리즘 구현 476
10.8.4 Prim의 MST 알고리즘 482
10.9 최단 경로(Shortest Path) 482
10.9.1 데익스트라(Dijkstra) 알고리즘 개요 483
10.9.2 최단 경로 값 구하기 484
10.9.3 최단 경로(shortest path) 추적하기 487
10.9.4 데익스트라 알고리즘 구현 489
10.9.5 A* 알고리즘 493
10.9.6 Floyd 알고리즘 495
연습문제 496

PART IV : 자료 구조 고급

CHAPTER 11 우선 순위 큐(priority queue) 499
11.1 정렬 알고리즘 501
11.1.1 선택 정렬(selection sorting) 502
11.1.2 병합 정렬(merge sorting) 504
11.2 우선 순위 큐 509
11.2.1 배열을 이용한 우선 순위 큐 510
11.2.2 연결 리스트를 이용한 우선 순위 큐 510
11.3 힙(heap) 511
11.3.1 힙의 연산 513
11.3.2 힙의 구현 515
연습문제 521

CHAPTER 12 해싱(hashing) 523
12.1 해싱의 기본 525
12.2 해시 함수(hash function)와 해시 테이블(hash table) 527
12.2.1 간단한 해시 함수: 자리 수 선택 528
12.2.2 간단한 해싱 함수 구현 529
12.3 충돌 해결책 531
12.3.1 오픈 어드레싱(open addressing) 531
12.3.2 체이닝(chainging) 532
12.3.3 체이닝을 이용한 해싱 구현 533
연습문제 542