알고리즘
1. 개요
문제를 해결하기 위한 절차나 방법. 이 단어는 아랍의 수학자인 알-콰리즈미의 이름에서 유래했다고 알려졌다. 영어로는 algorism보다는 algorithm(알고리듬)으로 훨씬 더 자주 쓰지만 한국에서는 알고리듬보다는 알고리즘의 사용 빈도가 높다.
알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다. 조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다.
컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저(진행절차)를 의미한다.
2. 알고리즘의 조건
알고리즘은 이하의 요건을 만족해야만 한다.
- 입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
- 출력 - 알고리즘은 최소 1개 이상의 결과를 가진다.
- 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
- 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다. 알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.
- 효과성 - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.
즉, 쉽게 말하면 알고리즘은 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고 효과적으로 입력에 따른 결과물을 도출 할 수 있다면 알고리즘으로 볼 수 있다는 의미이다. 반대로 명령에 애매함이 있다거나 유한한 시간 안에 끝나는 것이 보장되지 않은 경우를 메서드(Method)라고 한다. 예를 들어 '산에서 길을 잃었을때 계곡을 찾아서 아래로 내려간 뒤 물길을 따라 하류로 가면 된다.' 라는 문장은 메서드이다.
3. 알고리즘의 표현 방법
알고리즘은 크게 3개의 표현 방법을 가진다. 첫번째는 고차원적인 언어로 인간이 이해하기 쉬운 말로 설명되어 있는 형태이며, 두번째는 구현 상세 내역이며, 마지막으로는 인간이 꽤 알아먹기 힘든 튜링 머신의 Stable Table이라고 불리는 그림이나 출력물의 형태로 나타내는 방법이 있다.
4. 알고리즘의 평가
알고리즘이 위의 조건들을 모두 만족한다면 문제를 풀 수 있다고 할 수 있지만, '효과적으로' 풀어낸다고 할 수는 없다. 위에서 말한 유한한 시간이 몇 달 혹은 몇 년이 될 수도 있기 때문이다. 따라서 우리는 알고리즘을 효율성으로 평가하게 되고, 컴퓨터에서는 시간과 메모리라는 두 자원을 얼마나 소모하는지가 효율성의 중점이 된다.
- 시간 복잡도(time complexity)
알고리즘의 종류에 따라 시간복잡도의 평가기준도 다양하다. 일반적으로는 $O(n)$의 시간복잡도를 가지면 좋은 알고리즘으로 취급하며, $log(n)$의 지수승이 붙는 정도로 막으면($O(n log n)$ 등) 매우 바람직한 결과이다. $O(n^3)$ 정도만 돼도 큰 자료수에선 급격히 느려진다.
검색 알고리즘의 경우 $O(1)$이나 $O(log(n))$의 시간복잡도를 가지면 알고리즘을 선호한다.
이런 식으로 시간 복잡도가 n의 다항식 이하가 되는 알고리즘들을 다항 시간 알고리즘(polynomial time algorithm)이라고 한다. 여기까지만 보면 다항식과는 넘사벽의 증가속도를 자랑하는 $O(2n)$ 또는 $O(n!)$ 같은 알고리즘은 매우 막장인 것처럼 보이지만, 세상에는 이런 알고리즘밖에 방법이 없는 어려운 문제들이 수두룩하다. 이런 경우에는 정답을 포기하고 근사해를 구해주는 알고리즘을 찾게 된다. 더 자세한 이야기는 P-NP 문제 참고.
- 공간 복잡도(space complexity)
5. 알고리즘 목록
- 네트워크 플로우
- 문자열 검색
- 정렬
- 탐색
- 트리
- 최단거리
- 최소 스패닝 트리

- ISU 위키의 모든 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 제외)
- 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.