체험! 자료구조

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차원 배열 == 이미지(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