알고리즘

알고리즘(Algorithm)이란 어떤 일을 수행하는 과정을 순차적으로 제시한 모호함 없는 절차이며, 문제 해결을 위해 명령의 순서를 지정하는 것을 의미한다.

또한, 다음과 같은 성질을 만족한다.

• 유한성: 유한한 시간 안에 과정이 수행되어야 한다.
• 명확성: 각 단계에서 그 과정이 명확하게 기술되어야 한다.

알고리즘은 반드시 유한한 단계 이내에 종료(Halt)되어야 한다. 종료(Halt)란 더이상 다음 단계로 나아가지 못하는 상태를 의미한다.

실생활 속에서 다양한 알고리즘의 사용 예시를 찾아볼 수 있다. 예를 들어, 백과사전에서 원하는 항목을 찾기 위해 첫 페이지부터 차례대로 찾지 않고 목차나 색인을 훑어보며 찾는 행위는 인덱스 엔트리를 사용한 변형된 이진 탐색 알고리즘의 일종이라고 볼 수 있다.

동작

구조적 프로그래밍 정리에 따르면 모든 알고리즘은 다음 세 유형의 동작만으로 표현할 수 있다. 즉, 다음 세 가지 동작을 재귀적으로 조합하면 컴퓨터가 하는 모든 일을 나타낼 수 있다.

• 순차 동작(sequence): 한가지 동작을 수행한 후 다음 동작으로 이동한다.
• 조건 동작(selection): 단계를 수행하기 전 '조건'을 먼저 물어본 후, 조건에 따라서 다른 동작을 선택하여 수행한다.
• 반복 동작(repetition): 조건을 만족할 때까지 특정한 동작을 반복하여 수행한다.

효율성의 분석

알고리즘의 효율성의 분석은 알고리즘의 시간복잡도와 공간복잡도를 계산함으로서 분석할 수 있으며, 최악의 경우의 자원의 사용은 빅오 표기법을 통해서 나타낸다.

종류

해당 문제에 대하여 소개된 주요 알고리즘을 서술한다.

그래프 알고리즘(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)

• 타잔 알고리즘(Tajan's algorithm)
• 코사라주 알고리즘(Kosaraju's algorithm)

정렬 알고리즘(Sorting algorithms)

비교 정렬을 사용하는 알고리즘

이 경우 시간복잡도의 하한은 결정 트리를 통해서 $O(N\log {N})$임을 증명할 수 있다.

• 버블 정렬(Bubble sort)
• 병합 정렬(Merge sort)
• 퀵 정렬(Quick sort)
• 삽입 정렬(Insertion sort)

비교 정렬을 사용하지 않는 알고리즘

• 기수 정렬(Radix sort)