 |
|
|
|
 |
|
[책소개]
이책은 저자가 최근 대학교에서 전산전공 학생을 대상으로 "자료구조"라는 강좌로 강의한 내용을 중심으로 집필하였다. 책 내용은 "Program=tctures+Algorithm"이라는 명제 아래 자료구조에 알고리즘과 밀접한 관계에서 접근하였고 알고리즘의 효율성 또한 자료구조에 따라 평가하고 이를 개선하는 가이드 라인으로 정하였다.
따라서 이 책은 프로그램 작성과 분석이라는 측면과 프로그램 텍스트로 표현되는 알고리즘 구조에 중점을 두고 있다. 복잡하고 방대한 자료를 취급하는 경우 프로그래밍을 체계적이고 학문적으로 관찰하는 것이 대단히 중요하다. 왜냐하면 프로그램은 문제의 확실한 표현과 자료구조를 지원하는 추상적 알고리즘의 마지막 구체화에 속하기 때문이다. 즉, 자료의 구조는 자료에 응용되는 알고리즘에 대한 지식 없이는 접할 수 없고, 알고리즘의 구조와 선택은 자료구조에 긴밀하게 묶여 있다는 사실로부터 출발하고 있다.
이 책은 알고리즘으로부터 자료구조를 관찰하는 것이 아니라 자료구조로부터 알고리즘을 관찰하는 데 그 특징이 있다. 왜냐하면 데이터는 프로그램을 개발하는 과정에서 알고리즘보다 이전에 관찰되어야 하기 때문이다. 즉, 자료에 대한 연산 이전에 객체가 있어야 한다는 생각 때문이다. 또한 프로그램은 단순한 자료원소를 조작하는 이성적인 알고리즘에 집중하고 있기 때문에 자료구조로부터 알고리즘을 연결시켜야 한다.
이 책에서 알고리즘은 먼저 경험적 방법으로 정확성을 전제로 한 후, 점차로 효율성에 대한 분석을 통해 복잡도를 향상시키는 방법으로 알고리즘을 개선하도록 하였다.
근래에 와서 프로그래밍 기법에 객체 중심적인 경향이 있기 때문에 이 책은 알고리즘을 절차지향형 언어(C, Pascal 등)보다 객체지향형 언어인 Java로 서술하고 구현하였다. 따라서 예제 프로그램은 객체지향 특성인 캡슐화, 정보은폐, 추상화, 상속성, 재사용성 등을 고려하여 작성하였다.
책 전체는 8단원으로 구분하였고, 각 단원들은 전후단원에 직접적인 관계를 가지고 관찰할 수 있도록 나열하였다.
이 방법에 따라 이 책은 배열과 레코드와 같은 구조적 자료형으로부터 선형 리스트와 트리(tree)에 대해 다루었고, 다음에 자료의 이산적인 구조 즉, 그래프(graph)와 메모리관리 알고리즘에 대해 살펴보았으며, 알고리즘의 효율성에 따라 자료의 정렬과 탐색을, 그리고 파일구조를 중점적으로 다루었다.
이 책은 이론과 실습을 목표로 저술되었으며 java 언어를 잘 모르는 독자들을 위하여 java에 대한 부록을 책 뒤에 덧붙였다. 부록에 쓰여진 java 언어는 자료구조에 따른 알고리즘을 서술하는데 필요한 요소만을 다루었으며, Thread, GUI, Applet, Network 등에 대해서는 취급하지 않았다.
java 버전은 sdk1.3을 기준으로 했으며 상세한 것은 sdk1.3의 API 문서를 참조하기 바란다 (http://java.sun.com/j2se/1.3/docs/api/index.html).
이 책의 내용은 각 장별로 다음과 같은 내용으로 서술되었다.
1장에서는 프로그램은 자료구조와 알고리즘의 관계에서 단순한 문제해결이라는 점을 떠나서 자료구조에 따라 알고리즘이 다양하게 존재할 수 있다는 것과 이에 대한 알고리즘의 효율성을 논의하였다. 예를 들어 가계부관리 문제라든가 30 & 4 문제 등을 놓고 자료구조와 알고리즘이 얼마나 긴밀하게 연결되는지 보여주고 알고리즘의 분석을 통해서 실행시간과 소요되는 메모리 공간에 대한 효율성을 측정하는 방법에 대해 살펴보았다.
2장에서는 모든 프로그래밍 언어에서 가지고 있는 기본 자료형과 구조적 자료형인 배열, 레코드와 자바에서 제공되는 벡터형(Vector), 참조형, 추상적 자료형인 클래스형(class)과 재귀적 자료형에 대해 살펴보았다. 배열과 같은 순차적 구조를 가지고 있는 리스트의 연산시간과 메모리의 사용을 향상시키기 위한 자료구조에 대해 살펴보았고, 재귀적 자료형을 통해 연결리스트(linked list)의 구축과 이에 따른 효율성을 분석하였다.
3장에서는 재귀적 자료형을 통해 연결리스트를 구축하고 이를 이용하여 스택(stack)과 큐(queue) 리스트와 링(ring) 리스트 등을 구현하였다. 특히 스택은 java에서 지원하는 Stack이라는 클래스를 통하여 구현하였다.
4장에서는 리스트에서의 탐색이나 기타 연산이 구조상 순차적으로 진행되기 때문에 연산시간이 길다. 따라서 신속한 검색을 목적으로 트리(tree)구조를 도입하고, 트리구조에 따른 관련 연산의 효율성을 높일 수 있는 다양한 유형의 트리를 분석하고, 끝으로 신속한 탐색을 위한 트리 가운데 균형잡힌 이진 탐색트리(Balanced tree: AVL-tree)를 살펴보았다.
5장에서는 이산 자료구조의 대명사로써 일상생활의 모든 망(network)을 표현하는 그래프와 그의 연산 알고리즘을 살펴보았다. 그래프의 구현에서 시작하여 그래프에 대한 순행방법과 지점간을 연결하는 최소비용계산 문제라든지 한 지점에서 다른 지점에 이르기까지 최단 경로를 찾는 문제에 대해 살펴보았다.
6장에서는 자료의 기본적인 내부정렬 알고리즘의 복잡도 분석으로 효율성을 평가한 후에 개선 알고리즘을 제시하고 복잡도를 분석하였다. 그리고 파일에서의 정렬방법 중 외부정렬 알고리즘에 대해 다루었다.
또한 배열을 통해 이진트리(binary tree)와 전형적인 AVL 트리인 피보나치 트리(Fibonacci tree)의 탐색 알고리즘에 대해 살펴보았다.
7장에서는 자료구조상 프로그램 실행시간에 메모리를 동적으로 할당하고 회수하는 방법과 알고리즘(garbage collection / memory compaction)을 소개하였다.
8장에서는 정보처리에 있어서 효율적인 검색과 갱신 및 삭제와 삽입 등에 관련된 파일조직 (file organization)기법과 연산방법에 대해 살펴보았다.
이상 위에서 서술한 내용을 중심으로 기본적인 자료구조와 알고리즘을 java 언어로 구현하고 서술하였다. 비록 부족한 점이 있을지라도 이 책을 통하여 많은 학생들이 자료구조와 알고리즘을 이해하고 학습하는데 큰 도움이 되길 바라며, 앞으로 기회가 주어진다면, 부족한 부분을 보충하고 잘못된 부분을 수정하여 좀더 알찬 내용으로 거듭날 것을 약속드린다.
끝으로 이 책이 출판되기까지 적극적으로 협조해 주신 21세기사 이범만 사장님께 먼저 심심한 감사를 드리며, 탈고될 때까지 교정에 큰 몫을 해준 강원대학교 대학원 박사과정에 재학중인 서희정 양과 석사과정 이진수 군, 채영진 군에게 감사를 표하고, 또한 보이지 않는 곳에서 책을 출판하는 데에 최선을 다해 주신 편집부 및 출판부의 여러분께 깊이 감사를 드린다.
2000년 11월
저 자 씀
[목차]
제1장 입 문
1.1 자료구조와 알고리즘
1.2 실행시간 측정
1.3 객체지향 프로그래밍
제2장 자료형
2.1 기본 자료형
2.2 참조형
2.3 재귀적 용법
제3장 리스트
3.1 배열에 의한 순차 리스트
3.2 연결 리스트
3.3 스택과 큐
제4장 트리
4.1 트리 구현
4.2 이진트리 순행
4.3 탐색트리
4.4 AVL트리
제5장 그래프
5.1 그래프의 유형
5.2 용어 설명
5.3 그래프의 구현
5.4 그래프의 순행
제6장 정렬과 탐색
6.1 내부정렬
6.2 외부정렬
6.3 탐색
제7장 메모리 할당과 회수
7.1 메모리 수집방법
7.2 메모리 할당
7.3 메모리 융합
7.4 페이지 교환방법
제8장 파 일
8.1 파일의 설계
8.2 파일 조직
8.3 인덱스 순차파일
8.4 인덱스 파일
8.5 다중 링 파일
부록 자바 프로그래밍언어
1. 수식
2. 제어문
3. 클래스와 객체
4. 자료형
5. 실체변수
6. 객체생성
7. 메소드
8. 생성자
9. 매개변수 전달
10. package
11. interface
12. 자료형 변환
13. Exception
14. 입출력 클래스 |
|
|
|
