알고리즘(Algorithm)이란 어떤 일을 수행하는 과정을 순차적으로 제시한 모호함 없는 절차이며, 문제 해결을 위해 명령의 순서를 지정하는 것을 의미한다.
또한, 다음과 같은 성질을 만족한다.
- 유한성: 유한한 시간 안에 과정이 수행되어야 한다.
- 명확성: 각 단계에서 그 과정이 명확하게 기술되어야 한다.
알고리즘은 반드시 유한한 단계 이내에 종료(Halt)되어야 한다. 종료(Halt)란 더이상 다음 단계로 나아가지 못하는 상태를 의미한다.
실생활 속에서 다양한 알고리즘의 사용 예시를 찾아볼 수 있다. 예를 들어, 백과사전에서 원하는 항목을 찾기 위해 첫 페이지부터 차례대로 찾지 않고 목차나 색인을 훑어보며 찾는 행위는 인덱스 엔트리를 사용한 변형된 이진 탐색 알고리즘의 일종이라고 볼 수 있다.
종류
해당 문제에 대하여 소개된 주요 알고리즘을 서술한다.
그래프 알고리즘(Graph algorithms)
최단 경로 문제(Shortest path problem)
하나의 시작점에서 다수의 도달점으로 가는 최단 경로를 찾는 알고리즘
- 다익스트라 알고리즘(Dijkstra's algorithm)
- 벨만-포드 알고리즘(Bellman-Ford algorithm)
다수의 시작점에서 다수의 도달점으로 가는 최단 경로를 찾는 알고리즘(All-pairs shortest paths)
- 플로이드-워셜 알고리즘(Floyd–Warshall algorithm)
최소 스패닝 트리 문제(Minimum spanning tree problem)
- 크루스컬 알고리즘(Kruskal's algorithm)
- 프림 알고리즘(Prim's algorithm)
- Borůvka 알고리즘(Borůvka's algorithm)
강한 연결요소 문제(Strongly connected component problem)
정렬 알고리즘(Sorting algorithms)
비교 정렬을 사용하는 알고리즘
이 경우 시간복잡도의 하한은 결정 트리를 통해서 임을 증명할 수 있다.[1]
비교 정렬을 사용하지 않는 알고리즘
- 기수 정렬(Radix sort)
동작
구조적 프로그래밍 정리에 따르면 모든 알고리즘은 다음 세 유형의 동작만으로 표현할 수 있다. 즉, 다음 세 가지 동작을 재귀적으로 조합하면 컴퓨터가 하는 모든 일을 나타낼 수 있다.
- 순차 동작(sequence): 한가지 동작을 수행한 후 다음 동작으로 이동한다.
- 조건 동작(selection): 단계를 수행하기 전 '조건'을 먼저 물어본 후, 조건에 따라서 다른 동작을 선택하여 수행한다.
- 반복 동작(repetition): 조건을 만족할 때까지 특정한 동작을 반복하여 수행한다.
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 《Introduction to Algorithms》. MIT Press. 193쪽. ISBN 978-0-262-03384-8.