Chapter I 자료구조 공부를 위한 프로그래밍과 수학 기초
A. C 프로그래밍 기초
1. 배열(Array)
(1) 정적 배열
(2) 동적 배열
2. 포인터 변수와 포인터 연산
3. 구조체(Structure)와 공용체(Union)
(1) 구조체의 정의
(2) 공용체
4. 문자열
(1) 응용 1. 문자열 삽입 프로그램
(2) 응용 2. 문자열 패턴 매칭 프로그램
(3) 응용 3. strcat()을 사용하지 않고 두 개의 문자열을 합치는 프로그램
(4) 응용 4. 문자열을 역순으로 출력하는 프로그램
(5) 응용 5. 문자열에서 특정 문자의 출현 빈도 확인하는 프로그램
(6) 응용 6. strcpy()를 사용하지 않고 문자열을 복사하는 프로그램
B. 수학기초
1. 조합론적 원리
2. 지수와 로그(Exponentials and Logarithms)
3. 합계와 반복
4. 점진적 표기법
5. 랜덤화와 확률(Randomization and Probability)
Exercise
Chapter II 자료구조 기본 개념
1. 자료구조 용어 정리
(1) 문제, 알고리즘, 프로그램
(2) 데이터와 자료구조
2. 자료구조와 ADT
3. 알고리즘의 성능 분석과 복잡도(Complexity)
(1) 시간복잡도
(2) 공간복잡도
4. 점근적 알고리즘 분석과 점근표기법(???? ???? ???? asymptotic notation)
(1) ????(Big Oh)
(2) ????(Omega)
(3) ????(Theata)
(4) ???? ???? ????의 관계
(5) ????(Big Oh) 기반의 시간복잡도 클래스
5. 최적의 알고리즘
6. 대표적인 문제들의 복잡도
7. 병합 정렬
8. 자료구조 : 데이터의 조직
Exercise
Chapter III 재귀(Recursion)
1. 재귀의 기본 개념
2. 재귀와 반복의 차이
3. 재귀의 일반적인 오류
(1) 베이스 케이스 생략 오류
(2) 스택 오버플로우
(3) 진행 실패
4. 재귀의 복잡도
5, 응용 : 힐버트 곡선(Hilbert Curve) 문제
Exercise
Chapter IV 연결 리스트(Linked List)
1. 단일 연결 리스트
(1) 노드와 노드 구조체
(2) 연결 리스트의 정의와 시작
(3) 연결 리스트의 삽입
(4) 연결 리스트의 삭제
(5) 응용 1. 간단한 다항식 프로그램
(6) 응용 2. 이중 연결 리스트를 활용한 다항식 프로그램
2. 이중 연결 리스트 (Doubly Linked List)
(1) 이중 연결 리스트(Double Linked List)를 위한 노드 구조체
(2) 이중 연결 리스트에 노드 삽입
(2) 이중 연결 리스트에서 노드 삭제
(3) 응용 1. 이중 연결 리스트를 활용한 프로그램
3. 환형 연결 리스트 (Circularly Linked List)
(1) 응용 1. 이중 연결 리스트를 활용한 프로그램
Exercise
Chapter V 스택(Stack)
1. 스택 기본 연산
(1) 스택의 원소 정의와 초기화
(2) 스택이 비어있는지 가득 차 있는지 검사
(3) push()
(4) pop()
(5) 스택의 오류 처리
(6) 동적 배열을 사용하는 스택 구현
2. 응용
(1) 응용 1. 하노이 타워(Tower of Hanoi)
(2) 응용 2. N-퀸 문제(N-Queens Problem)
(3) 응용 3. 수식 표기법의 변환
3. 연결 스택
(1) 연결 스택의 구조
Exercise
Chapter VI 큐(Queue)
1. 배열을 사용한 큐의 구현
2. 정적 배열을 이용한 환형 큐(Circular Queue)
3. 동적 배열을 이용한 환형 큐
4. 연결 리스트를 이용한 큐
Exercise
Chapter VII 트리(Tree)
1. 트리의 표현
2. 이진 트리(Binary Tree)
(1) 이진 트리의 분류
(2) 이진 트리의 구현
(3) 이진 트리의 순회(Binary Tree Traversal)
3. 힙 트리(heap tree)
(1) 최대 힙에서 삽입
4, 우선순위 큐(priority queue)
(1) 정적 배열을 이용한 우선순위 큐 구현
(2) 힙을 이용한 우선순위 큐 구현
(3) 이진 탐색 트리를 이용한 우선순위 큐 구현
5. 힙 정렬(Heap Sort)
6. 이진 탐색 트리(Binary Search Tree, BST)
7. 선택 트리(Selection Tree)
(1) 승자 트리(winner tree)
(2) 패자 트리(loser tree)
8. 포리 트리
Exercise
Chapter VIII 정렬
1. 버블 정렬(Bubble Sort)
2. 선택 정렬(Selection Sort)
3. 삽입 정렬(Insertion Sort)
4. 합병 정렬(Merge Sort)
5. 퀵 정렬(Quick Sort)
(1) 삼분할 퀵 정렬
(2) 랜덤화 퀵 정렬
(3) 쓰리 미디언 퀵 정렬
(4) 비재귀적 퀵 정렬
(5) 중앙 피벗 퀵 정렬
6. 힙 정렬(Heap Sort)
7. 기수 정렬(Radix Sort)
8. 정렬 프로그램 통합
Exercise
Chapter IX 해싱
1. 정적 해싱 (Static Hashing)
(1) 해시 테이블의 예
(2) 해시 함수
(3) 해시 함수의 종류
(4) 충돌(Overflow) 처리
2. 동적 해싱
(1) 디렉터리를 사용하는 동적 해싱
(2) 디렉터리를 사용하지 않는 동적 해싱
Exercise
Chapter X 탐색(Searching)
1. 순차 탐색(Sequential Search)
2. 이진 탐색(Binary Search)
3. 색인 순차 탐색(Indexed Sequential Search)
4. 보간 탐색(Interpolation Search)
Chapter XI 이진 탐색 트리(Binary Search Tree)
1. AVL(Adelson Velsky Landis) 트리
(1) LL 회전 (Left-Left Rotation)
(2) LR 회전 (Left-Right Rotation)
(3) RR 회전 (Right-Right Rotation)
(4) RL 회전 (Right-Left Rotation)
(5) 이중 회전 알고리즘
2. 2-3 트리
(1) 2-3 트리의 삽입
(2) 2-3 트리의 삭제
3. 기타 이진 탐색 트리
(1) 2-3-4 트리
(2) 레드-블랙(Red-Black) 트리
Exercise
Chapter XII 그래프
1. 그래프 이론의 역사와 활용
2. 용어
3. 그래프의 표현 방법
4. 그래프 순회(Graph Traversal)
(1) 깊이 우선 탐색(DFS, Depth First Search)
(2) 너비 우선 탐색(BFS, Breath First Search)
5. 최단 경로 알고리즘(Shortest Path Algorithm)
(1) Dijikstra(다익스트라)의 최단 경로 알고리즘
(2) Bellman-Ford(벨만-포드)의 최단 경로 알고리즘
(3) Floyd(프로이드)의 최단 경로 알고리즘
6.최소 신장 트리(Minimum Spanning Tree)
(1) 크루스칼(Kruskal) 최소 비용 신장 트리
(2) 프림(Prim)의 최단경로 알고리즘
Exercise