1. 알고리즘의 주제별 분류
ㅇ 기초적인 알고리즘
- 최대값 또는 최소값 찾기 등
. 가장 큰 숫자를 기억해가며 진행함
- 유클리드 알고리즘
. 두 정수의 최대공약수를 빠르게 구하기
ㅇ 탐색 알고리즘 (Searching Algorithm)
- 탐색 문제
. 순서화된 리스트(ordered list)에서 어떤 원소의 위치 및 존재유무를 찾는 것
- 탐색문제의 해 또는 결과
. 원소의 위치
- 주요 종류
. 순차 탐색(sequential search)/선형탐색(linear search)
. 이진 탐색 (binary search) 등
* 보통, 자료구조 형태에 따라 구분됨
ㅇ 정렬 알고리즘 (Sorting Algorithm)
- 정렬 문제
. 수많은 자료를 특정 목적에 맞게 순서있게 재 배열하는 것
- 정렬문제의 해 또는 결과
. 정렬된 배열
- 주요 종류
. 선택 정렬 (Selection Sort)
. 버블 정렬 (Bubble Sort)
. 삽입 정렬 (Insertion Sort)
. 퀵 정렬 (Quick Sort)
. 병합 정렬 (Merge Sort)
ㅇ 그래프 알고리즘 (Graph Algorithm)
- 정점과 간선으로 구성된 구조를 탐색하거나 최적 경로, 연결성 등을 구하는 알고리즘
- 주요 종류
. 그래프 순회(Graph Traversal)/탐색,검색(Graph Search) 방법
. 신장 트리(생성 트리) 작성 방법
. 최소비용 생성트리 작성 알고리즘
. 최단경로 알고리즘
ㅇ 스트링 매칭 알고리즘 (String Matching Algorihm)
- 긴 텍스트에서 짧은 패턴 문자열이 어디에 있는지를 찾는 것
- 주요 종류 : KMP, Boyer-Moore, Rabin-Karp 등
ㅇ 해시 알고리즘 (Hash Algorithm)
- 데이터를 빠르게 검색,저장,비교할 수 있도록, 고정 길이의 해시값으로 변환
- 주요 종류 : 해시 테이블, 해시 함수, SHA, MD5 등
ㅇ 최적화 알고리즘 (Optimizing Algorithm) 등
- 제한된 조건 내에서 최대 또는 최소의 성능이나 결과를 도출하는 알고리즘
- 주요 종류 : 선형계획법, 유전 알고리즘, 경사하강법 등
2. 알고리즘에 확률의 개입 여부에 따른 분류
ㅇ 결정 알고리즘 (Deterministic Algorithm)
- 항상 정확한 답을 반환하는 알고리즘
- 例) 위 1.항에 언급된 대부분의 알고리즘들
ㅇ 확률 알고리즘 (Probabilistic Algorithm), 무작위 알고리즘 (Randomized Algorithm)
- 실행될 명령이 무작위로 결정되는 알고리즘
- 例)
. 몬테칼로 알고리즘 : 무작위로 난수를 발생시켜 근사적인 해를 구하는 알고리즘
. 라스베가스 알고리즘 : 무작위 시간으로 정확한 해를 구하는 알고리즘
3. 알고리즘의 설계 기법/설계 전략/설계 패러다임에 의한 분류
※ ☞ 알고리즘 설계 참조
- 분할정복 (Divide and Conquer) 전략
. 규모가 큰 문제를 만만한 작은 조각으로 나눠 각개격파
- 동적계획법 (Dynamic Programming) 전략
. 문제를 작은 부분 문제로 나누되, 동일 부분 문제의 반복 결과를 저장하여 중복 계산 방지
- 탐욕 알고리즘 (Greedy Algorithm) 전략 등
. 매 단계에서 가장 좋아 보이는 선택을 하는 방식