상세정보

알고리즘의 기본 개념과 용어를 쉽게 풀이하고 기본적인 자료구조에서어려운 자료구조에까지 그 원리와 C로 구현함에 있어서의 문제점을 상세히 소개하였다.

이 책은 1권과 2권으로 구성되어 있다. 1권의 내용은 주로 프로그램을 작성할 때 많이 사용하게 되는 "자료구조"에 관한 것. 기본적인 자료 구조라 할 수 있는 배열과 스택, 큐, 연결 리스트, 그리고 복잡한 자료 구조인 나무 구조, 우선 순위 큐 등을 다룬다. 주로 전산학과 2학년 과정에 포함되어 있는 "자료구조론"의 내용이다.

이에 비해 2권의 내용은 프로그램의 다른 측면인 "알고리즘"에 대한 것이다. 전산학과 3,4학년 과정에 해당하는 내용. 1권에서 배운 자료구조가 어떻게 실제로 활용되는지 보여주는 예들을 담았다.

C 문법책을 보았지만 어떻게 프로그램을 작성해야 할지 잘 모르는 초급자, 알고리즘의 벽을 넘지 못한 중급자에게 적당한 책이다.

정보제공 :

목차

제0장 일러두기

 0.1 저술의 기본 철학 = 19

 0.2 제한점 = 20

 0.3 각 장의 구성 = 21

 0.4 본서의 전체적인 구성 = 22

 0.5 용어 사용에 관한 문제 = 24

 0.6 소스 프로그램의 구성 = 25

제1장 개요

 1.1 알고리즘이란 무엇인가? = 27

  1.1.1 알고리즘의 정의 = 27

  1.1.2 알고리즘과 자료 구조 = 27

  1.1.3 어떤 알고리즘을 선택할 것인가? = 29

  1.1.4 알고리즘의 예 : 두 정수의 곱셈 = 30

 1.2 알고리즘의 분석(analysis of algorithm) = 32

  1.2.1 경험적 분석과 수학적 분석 = 32

  1.2.2 최악의 경우와 최선의 경우 = 33

  1.2.3 알고리즘 분석의 단계 = 33

  1.2.4 알고리즘의 유형 = 34

  1.2.5 O 표기법(Big-Oh notation) = 37

  1.2.6 다른 표기법 = 39

  1.2.7 시간 소요량과 공간 소요량 = 39

 1.3 유클리드의 알고리즘(Euclid's algorithm) : 최대공약수 찾기 = 40

  1.3.1 최대공약수(Greatest Common Divisor)란 = 40

  1.3.2 유클리드의 알고리즘 = 41

  1.3.3 C로 풀어본 유클리드 알고리즘 = 43

  1.3.4 유클리드 알고리즘의 개선 = 44

  1.3.5 알고리즘 실행 시간 측정 방법 = 46

  1.3.6 개선된 알고리즘의 측정 = 48

  1.3.7 결과의 분석 = 51

  1.3.8 어떤 알고리즘을 선택할 것인가? = 52

 1.4 소수를 구하는 알고리즘 = 53

  1.4.1 정의에 의한 알고리즘 = 53

  1.4.2 정의에 의해 소수를 구하는 프로그램 = 54

  1.4.3 개선된 알고리즘 = 55

  1.4.4 각 알고리즘의 성능 비교 = 56

  1.4.5 소수 구하기 알고리즘의 분석 = 58

  1.4.6 에라토스테네스의 체 = 59

  1.4.7 문제에 대한 이해가 필요하다 = 62

 1.5 최적화에 관하여 = 62

  1.5.1 최적화 기법 = 62

 1.6 결론 = 63

제2장 C 언어

 2.1 컴퓨터 언어의 흐름 = 65

  2.1.1 가장 비참했던 시절 = 66

  2.1.2 스파게티 코드 = 66

  2.1.3 구조화의 물결 = 67

 2.2 어려운 개념들 = 68

  2.2.1 데이터 추상화(data abstraction) = 68

  2.2.2 코드 추상화(code abstraction) = 69

  2.2.3 절차적 언어(Procedural programming language) = 70

  2.2.4 객체 지향 언어(Object Oriented Programming Language) = 72

 2.3 왜 C 언어인가? = 73

  2.3.1 C 언어의 특징 = 74

  2.3.2 C 언어의 기본 요소 = 75

  2.3.3 C의 함수 = 79

 2.4 포인터(Pointer) = 80

  2.4.1 포인터란 도대체 무엇인가? = 80

  2.4.2 포인터 연산자 = 81

  2.4.3 구조체를 가리키는 포인터 = 83

  2.4.4 포인터의 포인터 = 84

  2.4.5 void 포인터 = 86

  2.4.6 함수 포인터 = 88

  2.4.7 값에 의한 호출 대 참조에 의한 호출 = 89

  2.4.8 데이터형에 관계없는 swap() 함수 제작 = 92

 2.5 터보 C의 발전 = 93

제3장 자료 구조(Data structure)

 3.1 자료 구조란 무엇인가? = 95

 3.2 배열(array) = 96

  3.2.1 1차원 배열(one dimensional array) = 97

  3.2.2 다차원 배열(multi-dimensional array) = 98

  3.2.3 1차원 배열을 함수의 인자로 넘기는 방법 = 99

  3.2.4 2차원 배열을 함수의 인자로 넘기는 방법 = 101

  3.2.5 다차원 배열을 함수의 인자로 넘기는 방법 = 105

 3.3 미로에 갖힌 생쥐 = 106

  3.3.1 어떻게 작성할 것인가? = 106

  3.3.2 미로의 정의와 그리기 = 106

  3.3.3 우선법(right hand on wall) = 111

  3.3.4 최단 경로 찾기 = 115

  3.3.5 실행파일 = 119

 3.4 연결 리스트(Linked List) = 124

  3.4.1 단순 연결 리스트(Simple Linked List) = 125

  3.4.2 환형 연결 리스트(Circular Linked List) = 141

  3.4.3 이중 연결 리스트(Doubly Linked List) = 144

 3.5 단순 연결 리스트 응용 : 명함 관리 = 155

  3.5.1 프로그램의 구상, 입·출력 정의, 한계 = 155

  3.5.2 자료 구조의 생성 = 156

  3.5.3 입력, 삭제, 검색 함수 = 157

  3.5.4 연결 리스트의 디스크 입·출력 = 159

  3.5.5 방향 재설정(Redirection)을 이용한 출력 함수 = 162

  3.5.6 완전한 리스트 = 164

  3.5.7 개선할 점 = 169

 3.6 이중 연결 기스트 응용 : 텍스트뷰어 = 170

  3.6.1 설계와 한계 = 170

  3.6.2 자료 구조의 정의 = 171

  3.6.3 문자열을 파일에서 읽고 저장하기 = 172

  3.6.4 화면 출력 함수 = 174

  3.6.5 키 조작 함수 = 176

  3.6.6 완전한 리스트 = 178

  3.6.7 개선할 점 = 183

 3.7 스택(Stack) = 184

  3.7.1 스택의 개념 = 184

  3.7.2 배열로 구현하는 스택 = 185

  3.7.3 연결 리스트를 이용한 스택의 구현 = 190

  3.7.4 정리 = 197

  3.7.5 스택의 활용 = 197

 3.8 스택의 응용 : CALC 유틸리티 작성 = 198

  3.8.1 수식의 표기법 = 198

  3.8.2 중위표기법을 후위표기법으로 변환하는 방법 1 = 199

  3.8.3 중위표기법을 후위표기법으로 변환하는 방법 2 = 202

  3.8.4 후위표기법 수식의 평가 = 206

  3.8.5 CALC의 완전한 리스트 = 209

 3.9 큐(Queue) = 214

  3.9.1 큐의 개념 = 214

  3.9.2 배열을 이용한 큐의 구현 = 215

  3.9.3 연결 리스트를 이용한 큐의 구현 = 223

  3.9.4 정리 = 229

  3.9.5 큐의 응용 = 230

 3.10 나무(Tree) = 230

  3.10.1 나무 구조에서 사용하는 용어들 = 231

  3.10.2 나무의 성질 = 234

  3.10.3 이진 나무 구조의 표현 = 235

  3.10.4 이진 나무타기 : 순회(Tree traverse) = 236

  3.10.5 정리 = 249

 3.11 나무 구조의 응용 : 수식 나무(Parse tree) = 250

  3.11.1 후위표기법에서 수식 나무를 구성하는 방법 = 250

  3.11.2 완전한 리스트 = 254

  3.11.3 실행 결과의 분석 = 260

  3.11.4 발전시킬 점 = 260

제4장 재귀 호출(Recursion)

 4.1 자기자신을 호출한다 = 263

  4.1.1 잘못된 재귀 호출 = 264

  4.1.2 재귀 호출의 요건 = 265

  4.1.3 누승을 구하는 재귀 함수 = 266

  4.1.4 피보나치 수열을 구하는 재귀 함수 = 267

  4.1.5 재귀 호출의 전략 = 268

  4.1.6 하노이의 탑 = 269

 4.2 재귀 함수를 비재귀 함수로 바꾸기 = 274

  4.2.1 재귀 호출이 하나인 경우 = 274

  4.2.2 재귀 호출이 둘인 경우 1 = 275

  4.2.3 재귀 호출이 둘인 경우 2 = 278

  4.2.4 재귀 호출이 둘인 경우 3 = 282

  4.2.5 그 외의 경우 = 286

  4.2.6 새로운 접근 방법으로 비재귀판을 만드는 경우 = 287

  4.2.7 주의점 = 288

 4.3 그래픽에서의 활용 = 289

  4.3.1 선 그리기 = 290

  4.3.2 영역의 내부를 칠하기 = 292

 4.4 프랙탈 그래픽 = 298

  4.4.1 양탄자 모양 = 298

  4.4.2 프랙탈 나무 = 303

 4.5 파일 찾기 프로그램 RFF = 310

  4.5.1 findfirst(), findnext()의 사용법 = 310

  4.5.2 findfirst()와 findnext()로 디렉토리를 찾는 법 = 311

  4.5.3 findfile() 함수 = 311

  4.5.4 RFF.C의 완전한 리스트 = 312

  4.5.5 조언 = 314

 4.6 결론 = 315

제5장 정렬 알고리즘

 5.1 개요 = 317

  5.1.1 정렬의 방법론 = 318

  5.1.2 정렬 알고리즘의 다양성 = 319

  5.1.3 안정성(Stability) = 320

  5.1.4 일반화된 정렬 함수 = 321

 5.2 선택 정렬(Selection Sort) = 321

  5.2.1 선택 정렬 알고리즘 = 321

  5.2.2 select＿sort() 함수 = 323

  5.2.3 선택 정렬의 과정 = 324

  5.2.4 안정성 문제 = 325

  5.2.5 선택 정렬 알고리즘의 실행 시간 분석 = 325

  5.2.6 최적화 기법 = 326

  5.2.7 일반적인 함수 제작 = 326

 5.3 삽입 정렬(Insertion Sort) = 329

  5.3.1 삽입 정렬의 전략 = 329

  5.3.2 삽입 정렬의 실제 = 329

  5.3.3 C로 구현한 삽입 정렬 = 331

  5.3.4 삽입 정렬의 분석 = 332

  5.3.5 삽입 정렬의 최적화 = 333

  5.3.6 간접 정렬 = 335

  5.3.7 일반화된 함수 작성 = 337

 5.4 거품 정렬(Bubble Sort) = 338

  5.4.1 거품 정렬의 전략 = 338

  5.4.2 거품 정렬의 실제 = 339

  5.4.3 C로 구현한 거품 정렬 = 340

  5.4.4 거품 정렬의 분석 = 341

  5.4.5 거품 정렬의 개선 = 342

  5.4.6 일반화된 함수 작성 = 344

 5.5 쉘 정렬(Shell Sort) = 345

  5.5.1 쉘 정렬의 전략 = 345

  5.5.2 쉘 정렬의 실제 = 346

  5.5.3 C로 구현한 쉘 정렬 = 347

  5.5.4 쉘 정렬의 분석 = 348

  5.5.5 쉘 정렬의 개선 = 349

  5.5.6 일반화된 함수 작성 =351

 5.6 분포수세기(Distribution Counting) = 352

  5.6.1 분포수세기의 전략 = 352

  5.6.2 분포수세기의 실제 = 353

  5.6.3 C로 구현한 분포수세기 = 354

  5.6.4 분포수세기의 분석 = 355

 5.7 퀵 정렬(Quick Sort) = 356

  5.7.1 퀵 정렬의 전략 = 356

  5.7.2 퀵 정렬의 실제 = 357

  5.7.3 C로 구현한 퀵 정렬 = 359

  5.7.4 퀵 정렬의 분석 = 360

  5.7.5 퀵 정렬의 개선 1 : 비재귀판 = 361

  5.7.6 퀵 정렬의 개선 2 : 난수 분할 = 364

  5.7.7 퀵 정렬의 개선 3 : 삽입 정렬 = 366

  5.7.8 퀵 정렬의 개선 4 : 세 값의 중위 = 368

  5.7.9 qwort() 함수 = 370

  5.7.10 일반화된 함수 작성 = 371

 5.8 기수 정렬(Radix Sort) = 374

  5.8.1 기수 교환 정렬(Radix Exchange Sort)의 전략 = 375

  5.8.2 기수 교환 정렬의 실제 = 376

  5.8.3 C로 구현한 기수 교환 정렬 = 377

  5.8.4 기수 교환 정렬의 분석 = 379

  5.8.5 기수 교환 정렬의 개선(비재귀판) = 380

  5.8.6 직접 기수 정렬(Straight Radix Sort)의 전략 = 381

  5.8.7 직접 기수 정렬의 실제 = 382

  5.8.8 C로 구현한 직접 기수 정렬 = 383

  5.8.9 직접 기수 정렬의 분석 = 384

  5.8.10 두가지 기수 정렬법의 일반화 = 386

 5.9 힙 정렬(Heap Sort) = 386

  5.9.1 우선순위 큐(Priority Queue)란 = 386

  5.9.2 힙(Heap)이란? = 387

  5.9.3 나무 구조를 배열로 구현하는 법 = 390

  5.9.4 힙 정렬의 전략 = 392

  5.9.5 힙 정렬의 실제 = 393

  5.9.6 C로 구현한 힙 정렬 = 394

  5.9.7 힙 정렬의 분석 = 397

  5.9.8 힙 정렬의 개선 : 상향식 힙 생성 = 398

  5.9.9 일반화한 힙 정렬 = 401

 5.10 병합 정렬(Merge Sort) = 402

  5.10.1 병합이란? = 403

  5.10.2 병합 정렬의 전략 = 405

  5.10.3 병합 정렬의 실제 = 405

  5.10.4 C로 구현한 병합 정렬 = 407

  5.10.5 병합 정렬의 분석 = 409

  5.10.6 병합 정렬의 개선 = 410

  5.10.7 일반화한 병합 정렬 = 411

 5.11 외부 정렬(External Sort) = 412

  5.11.1 외부 장치의 특성 = 413

  5.11.2 외부 정렬의 전략 = 413

  5.11.3 외부 정렬의 실제 = 414

  5.11.4 C로 구현한 외부 정렬 = 417

  5.11.5 외부 정렬의 분석 = 419

  5.11.6 간접 정렬 방법 = 420

 5.12 정리 = 421

  5.12.1 정렬 라이브러리(sort.c) = 421

  5.12.2 정렬 라이브러리 헤더 파일 = 432

  5.12.3 정렬 라이브러리의 사용법 = 433

  5.12.4 실행 방법 = 439

  5.12.5 시간 측정 결과 = 440

  5.12.6 결론 = 442

제6장 검색(Searching Algorithm)

 6.1 검색(Searching) 일반론 = 443

  6.1.1 검색이 사용되는 경우 = 444

  6.1.2 검색 알고리즘 = 초기화+삽입+삭제+검색 = 444

  6.1.3 검색 알고리즘의 일반화 = 445

 6.2 순차 검색(Sequential Search) = 446

  6.2.1 순차 검색의 전략 = 446

  6.2.2 순차 검색의 삽입과 삭제 = 447

  6.2.3 C로 구현한 순차 검색 = 448

  6.2.4 순차 검색의 분석 = 450

  6.2.5 순차 검색의 개선 = 450

  6.2.6 순차 검색 라이브러리 = 451

  6.2.7 순차 검색 라이브러리의 소스 = 453

  6.2.8 연결 리스트를 위한 순차 검색 라이브러리 = 456

  6.2.9 연결 리스트를 위한 순차 검색 라이브러리의 구현 = 457

  6.2.10 연결 리스트를 위한 순차 검색 라이브러리 소스 = 459

 6.3 이분 검색 = 462

  6.3.1 이분 검색의 전략 = 462

  6.3.2 이분 검색의 실제 = 463

  6.3.3 C로 구현한 이분 검색 = 464

  6.3.4 이분 검색의 삽입과 삭제 = 464

  6.3.5 이분 검색의 분석 = 466

  6.3.6 이분 검색의 개선 : 보간법 이용 = 466

  6.3.7 이분 검색 라이브러리 = 471

  6.3.8 이분 검색 라이브러리의 소스 = 472

 6.4 이진 나무 검색 = 475

  6.4.1 이진 나무 검색의 전략 = 475

  6.4.2 C로 구현한 이진 나무 검색 = 477

  6.4.3 이진 나무 검색의 삽입 = 478

  6.4.4 이진 나무 검색의 삭제 = 480

  6.4.5 이진 나무 검색에서의 삭제를 개선 = 486

  6.4.6 이진 나무 검색의 분석 = 488

  6.4.7 이진 나무 정렬 = 489

  6.4.8 이진 나무 검색의 균형잡기 = 490

  6.4.9 이진 나무 검색 라이브러리 = 493

  6.4.10 이진 나무 검색 라이브러리 소스 = 497

  6.4.11 단어세기 문제 = 504

  6.4.12 실행 방법과 결과 = 508

 6.5 균형잡는 나무 검색(Balanced search tree) = 510

  6.5.1 AVL 나무 = 510

  6.5.2 2 - 3 나무 = 515

  6.5.3 2 - 3 - 4 나무 = 518

  6.5.4 빨강 - 검정 나무의 기본 = 527

  6.5.5 빨강 - 검정 나무의 회전 = 530

  6.5.6 빨강 - 검정 나무의 삽입 = 532

  6.5.7 빨강 - 검정 나무의 삭제 = 534

  6.5.8 C로 구현한 빨강 - 검정 나무 = 540

  6.5.9 균형잡는 나무 구조들의 분석 = 549

  6.5.10 빨강 - 검정 나무 라이브러리 = 550

  6.5.11 빨강 - 검정 나무 라이브러리 소스 = 551

  6.5.12 빨강 - 검정 나무 라이브러리 응용 = 561

 6.6 해쉬(Hash) = 562

  6.6.1 해쉬의 전략 = 562

  6.6.2 해쉬 함수의 작성법 = 563

  6.6.3 선형 검색법(Linear Probing) = 564

  6.6.4 C로 구현한 선형 검색법 = 568

  6.6.5 선형 검색법의 개선 = 570

  6.6.6 이중 해쉬법(Double Hash) = 571

  6.6.7 연결법(Separate chaining) = 572

  6.6.8 C로 구현한 연결법 = 575

  6.6.9 해쉬 검색의 분석 = 578

  6.6.10 해쉬 검색 라이브러리 = 579

  6.6.11 해쉬 검색 라이브러리 소스 = 580

  6.6.12 해쉬 검색 라이브러리의 사용법 = 584

 6.7 기수 검색 = 586

  6.7.1 이진 기수 나무 검색의 전략 = 586

  6.7.2 이진 기수 나무의 삽입 = 588

  6.7.3 이진 기수 나무의 삭제 = 589

  6.7.4 C로 구현한 이진 기수 나무 검색 = 590

  6.7.5 이진 기수 나무 검색의 분석 = 593

  6.7.6 이진 기수 트라이 검색의 전략 = 593

  6.7.7 이진 기수 트라이의 삽입 = 595

  6.7.8 이진 기수 트라이의 삭제 = 597

  6.7.9 C로 구현한 이진 기수 트라이 = 599

  6.7.10 이진 기수 트라이의 개선 = 603

 6.8 외부 검색 = 605

 6.9 정리 = 645

부록

 부록 1 Turbo C 라이브러리 함수 분석 = 649

  A1.1 표준 입·출력 함수 = 649

  A1.2 직접 화면 입·출력 함수 = 650

  A1.3 디스크 입·출력 함수 = 651

  A1.4 메모리 관리 함수 = 656

  A1.5 문자열 처리 함수 = 657

  A1.6 그래픽 함수 = 658

  A1.7 BIOS 제어 함수 = 663

  A1.8 변환 함수 = 665

  A1.9 정렬, 검색 함수 = 666

  A1.10 수학 함수 = 667

  A1.11 기타 = 668

 부록 2 키보드 스캔 코드 정의 파일 = 669

 부록 3 알파벳 문자 코드 = 673

 부록 4 하드 카피 함수 = 674

 부록 5 소스 디스캣의 구성 = 681

찾아보기 = 691