[알고리즘]알고리즘 총정리 슈퍼서브

소개

지난 한 학기 동안 열심히 작성한 자료입니다.

목차

제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 문제의 정복

본문내용

1. 알고리즘의 정의와 표현

알고리즘이란?

다음의 조건을 만족하는 특정한 일을 수행하는 유한개로 구성된 명령어들의 리스트 입력 : 0개 이상의 외부 자료 입력
출력 : 1개 이상의 자료 출력
명확성(definiteness) : 각 명령어는 분명하고 모호하지 않아야 한다.
유한성(finiteness) : 일정한 명령의 수행후에는 종료해야 한다.
유효성(effectiveness) : 각 명령어는 기본적이고 실행가능해야 한다.

알고리즘의 예

유클리드 호제법 (Euclidean algorithm)

int gcd(int u, int v)
{
while (u > 0) {
if (u < v) SWAP(u, v);
u = u - v;
}
return v;
}

다음의 프로그램은 알고리즘인가?
[3N + 1 문제]
read N
while (N != 1) {
if (N is even)
N = N / 2;
else
N = 3*N + 1;
}

알고리즘적인 문제 (algorithmic problem)

해답의 정확성에 대한 검증이 명백히 이루어질 수 있는 문제
알고리즘적인 문제의 예

문제명 : 최대공약수 문제
인스탄스(instance) : 양의 정수 A와 B
질문(question) : A와 B를 동시에 나누는 정수중에서 가장 큰 수를 구하시오.

문제명 : 부분 집합의 합
인스탄스 : N개의 양수의 집합 X와 양수 C
질문 : X의 부분집합들 중 그 합이 C와 일치하는 것이 존재하는가?

알고리즘의 유형

(정확한) 알고리즘 (exact algorithm)
근사 알고리즘 (approximation algorithm; Heuristics)
(결정적) 알고리즘 (deterministic algorithm)
확률 알고리즘 (램덤화 알고리즘)
(결정적) 알고리즘 (deterministic algorithm)
비결정적 알고리즘 (nondeterministic algorithm)
(순차적) 알고리즘 (sequential algorithm)
병렬 알고리즘 (parallel algorithm)
분산 알고리즘 (distributed algorithm)
그래프 알고리즘, 기하 알고리즘, 문자열 알고리즘, 행렬 알고리즘 등

참고자료

· 교재 및 강의노트