[알고리즘 요약, 알고리즘] 알고리즘 요점정리 서브노트

소개글

[알고리즘 요약, 알고리즘] 알고리즘 요점정리 서브노트에 대한 보고서 자료입니다.

목차

제1장 알고리즘의 소개
1. 알고리즘의 정의와 표현
2. 알고리즘의 분석
3. 수학적 기초
4. 기본 자료구조

제2장 정렬과 선택
1. 기본 정렬 알고리즘
2. 퀵 정렬과 합병 정렬
3. 정렬 문제의 복잡도
4. 힙 정렬 (Heap Sort)
5. 기수 정렬 (Radix Sorting)
6. 선택 문제 (Selection Problem)

제3장 탐색과 고급 자료구조
1. 기본 탐색 알고리즘
2. 해싱 (hashing)
3. 균형 탐색 트리 (Balanced Search Trees)
4. B-트리와 트라이
5. 힙 구조 (Heap Structures)
6. 분리된 집합을 위한 자료구조

제4장 알고리즘 설계 기법
1. 분할 정복법 (Divide and Conquer)
2. 욕심쟁이법 (Greedy Method)
3. 동적계획법 (Dynamic Programming)
4. 임시퇴각법 (Backtracking)

제5장 그래프 알고리즘
1. 정의 및 표현
2. 탐색과 응용
3. 스패닝 트리
4. 최단 경로 문제
5. 네트워크 흐름 문제

제6장 기하 알고리즘
1. 기본 알고리즘
2. 볼록 외피 문제
3. 교차 문제
4. 범위 탐색 문제

제7장 문자열 탐색 알고리즘
1. 유한 오토마타의 이용
2. KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
3. The Boyer-Moore 알고리즘

제8장 파일 압축 알고리즘
1. 호프만 코드 (Huffman Code)
2. Ziv-Lempel 코드

제9장 NP-Complete 문제
1. P와 NP
2. NP-complete 문제의 증명
3. NP 문제의 정복

본문내용

없음
특수한 파일(예, LISP, C 프로그램)에 대해서는 나쁜 압축률
적응 호프만 인코딩 (Adaptive Huffman Encoding)
형제 원칙 (Sibling Property)
트리의 단말 노드를 Top-Down, Right-to-Left 순으로
빈도수가 감소하도록유지
One Pass로 구성
문자 코드를 저장할 필요가 없음 - 압축과 해독 과정이 같음
적응 호프만 트리 구성의 예
∑ = {a, b, c, d, e, f}
입력 순서 = ( a a f c c c b d )
0-node : ∑'에 대응되는 노드
Output : 입력된 문자에 대응되는 노드의 코드, 또는
0-node에 대응되는 노드의 코드 + 0-node에서 문자의 위치 + 0
Input: a 1 b 2 f
Output: 10 1 01
(a b c d e f) 0 1 0 2
(f b c d e) a (f b c d e) a
3 4 5
1 2 c 2 2 c 3 2
a 001110 a 001 a
0 1 1 1 2 1
(e b c d) f f f
0 1 0 2
(e b d) c (e b d) c
5 5 8
⇒ 3 2 ⇒ 2 3 3 5
a a c
2 2 1 2 2 3
c c a
0 1 0 1 1 2
(e b d) f (e b d) f f
1 1
b
0 1
(e) d
출력 : 101010001110001111001101000110
2. Ziv-Lempel 코드
빈번하게 나오는 문자열(단어)을 한 코드로 표현하여 압축
심볼 버퍼 (symbol buffer) 유지
One Pass로 구성
문자 또는 문자열 코드를 저장할 필요 없음 - 압축과 해독 과정이 같음
UNIX 명령 compress에 해당 (호프만 코드: pack, 적응 호프만 코드: compack)
Ziv-Lempel 알고리즘 (Welch 1984)
1.모든 문자를 표(버퍼)에 넣는다.
2.문자열 s를 입력의 첫 번째 문자로 지정한다.
3.while 입력이 남아 있으면 do
4.문자 c를 읽는다.
5.if s+c가 표에 있으면 then
6.s = s + c
7.else
8.s의 코드를 출력한다.
9.s+c를 표에 넣는다.
10.s = c
11.endif
12.endwhile
13.s의 코드를 출력한다.
인코딩 예
∑ = {a, b, c, d}
입력 순서 = ( a a b a b a c b a a c b a a d a a )
순서




1
2
3
4
5
6
7
8
9
10
버퍼
a
b
c
d
aa
ab
ba
aba
ac
cb
baa
acb
baad
da
a
b
c
d
1a
1b
2a
6a
1c
3b
7a
9b
11d
4a
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
출력 : ( 1 1 2 6 1 3 7 9 11 4 5 )
제9장 NP-Complete 문제
1. P와 NP
최적화 문제(combinatorial optimization problem)와 결정 문제(decision problem)
(예) 상자 펙킹 문제 (bin packing problem)
OP : 물건을 전부 담을 수 있는 상자의 최소 개수를 구하라.
DP : 주어진 k개의 상자에 물건을 전부 담을 수 있는가?
접근 가능 문제(tractable problem)와 접근 불가능 문제(intractable problem)
결정 알고리즘(deterministic algorithm)과 비결정 알고리즘(nondeterministic algorithm)
문제의 부류
P 부류 : 다항 시간의 결정 알고리즘이 존재하는 문제 부류
NP 부류 : 다항 시간의 비결정 알고리즘이 존재하는 문제 부류
P ∈ NP, but P = NP (?)
2. NP-complete 문제의 증명
문제의 변형 (reduction; transformation)
문제 P1의 입력을 문제 P2의 입력으로 바꾸는 함수를 T라고 하자.
P1의 각 입력을 P2의 입력으로 바꾸는 함수 T의 수행 시간이 다항시간이고 P2에서의 해답이 P1에서도 해답이 될 수 있으면, T를 P1에서 P2로 다항시간-변형가능한 함수라고 부른다
P1 ∝ P1 : P1은 P2로 변형가능하다.
NP-Complete 문제
A problem P is NP-complete if
it is in NP and for every other problem P' in NP, P' ∝ P.
If any NP-complete problem is in P, then P = NP.
The CNF-satisfiability problem is NP-complete. (Cook's theorem)
A problem P is NP-complete if
P is in NP and the CNF-satisfiability problem ∝ P.
A problem P is NP-complete if
P is in NP and any known NP-complete problem ∝ P.
NP-hard 문제
A problem P is NP-hard if
an NP-complete problem ∝ P, but we don't know the P is in NP.
NP-complete 문제의 예
Graph coloring
Job scheduling with penalties
Bin packing
0/1 Knapsack
Subset sum
Partition
Hamiltonian path and cycle
Traveling salesman problem
3. NP 문제의 정복
정확한 해를 구하는 알고리즘
문제 크기가 매우 작은 경우에 한함
보통 임시퇴각법이나 분기한정법 이용
근사 알고리즘 (approximation algorithm)
최적화 문제에 대한 근사해를 구하는 알고리즘
근사비 (approximation ratio)
최적해에 대한 근사해의 비
근사비의 분석 어려움
(예)Bin Packing 문제
그래프 색칠하기 문제
외판원 문제
최적화 알고리즘 (optimization algorithm)
의사 담금질 (simulated anneling)
유전자 알고리즘 (genetic algorithm)

키워드

알고리즘,   알고리즘 정리,   알고리즘 요약,   알고리즘 시험,   알고리즘 설계,   그래프 알고리즘,   기하 알고리즘,   dkfrhflwma