알고리즘(Algorithm)은 어떤 문제를 풀기 위하여 명확하게 서술된 조건대로 수행하여 유한한 시간 안에 끝나는 것이 보장된 일련의 과정/방법을 뜻한다.
알고리즘의 어원은 중동 페르시아 지역에서 활동한 수학자 알 콰리즈미의 이름을 따서 붙였으며 이는 아라비아 숫자를 가리키는 알고리슴(Algorism)과 어원이 같다.
기록으로 남은 최초의 알고리즘은 그리스의 수학자 유클리드가 고안한 유클리드 호제법이다.
알고리즘은 사람의 수동 작업(인력) 혹은 컴퓨터의 연산력을 이용해 수행한다. 따라서 수학자들과 컴퓨터공학자들은 자원을 덜 소모하는 더 좋은 알고리즘을 찾는다.
알고리즘끼리 비교할 때 좋은 알고리즘은 일반적으로 범용적인 조건에서 더 효율적인 알고리즘으로 정의되며 이때 효율을 평가하는 잣대로 시간 복잡도와 공간 복잡도가 있다.
시간복잡도와 Big-O 표기법
편집시간 복잡도는 문제 풀이에 투입된 자료의 수가 증가할수록 걸리는 시간 증가분의 경향이다.
일반적으로 시간 복잡도는 Big-O 표기법을 사용해 표기한다. Big-O 표기법이란 특정한 자료 개수 이상의 자료가 주어졌을 때 어떤 알고리즘의 시간이 항상 특정한 함수 g(n)에 비해 적은 시간을 소모할 경우 양의 계수를 갖는 그 특정한 함수의 최상위 항 g에 대해 그 알고리즘의 시간 함수 f = O(g)로 시간 복잡도를 표시하는 방법이다.
이때 g(n)의 최상위 항을 제외한 다른 항이나 g의 계수는 O(g)에 영향을 주지 못하므로 생략된다. 가령 O(n2) = O(3n2) = O(4n2 + 50n + 4)이다. 그러므로 알고리즘들은 O(1), O(nk), O(log n), O (n * log n), O(2n) 같이 O 내부의 식이 단항식의 형태로 표현된다.
이것 말고도 Ω와 Θ도 있는데 g = Ω(f)는 f = O(g)이며, Θ의 경우 f= O(g)이고 f = Ω(g)인 경우를 뜻한다.
시간복잡도 예제
편집- 정수의 덧셈은 각 자리의 두 수를 더하고 필요하면 받아올림(carry)을 하기 때문에 더하는 두 숫자의 최대 자리수의 크기 n에 따라 결정되고 따라서 O(n)이다.
- 정수의 곱셈은 한 수의 각 자리마다 다른 수의 모든 자리의 수를 곱해야 하기 때문에 최대 자리수 n 곱하기 n에 비례하고 따라서 O(n2)이다. 이는 초등학교에서 배우는 나눗셈의 알고리즘에도 적용된다.
- RSA 암호화에 사용하는 modular exponentiation의 경우 O(n3)이 걸린다. 그러나 이를 역으로 RSA의 modular exponentiation에 사용한 숫자를 알아내려면 시간이 굉장히 오래 걸리는 브루트 포스를 써야 한다.
공간 복잡도
편집공간 복잡도는 문제 풀이에 필요한 데이터의 저장소의 크기의 증가분의 경향이다. 시간 복잡도와 같은 Big-O 표기법을 사용한다.
일반적으로 재귀를 사용하는 알고리즘(예: 다익스트라 알고리즘을 포함한 DFS 계열 알고리즘, DFS를 수행할 때 스택 자료구조를 사용하기 때문에 재귀를 반복할 수록 공간 복잡도가 증가한다)이나 메모이제이션을 사용하는 동적 계획법 같은 경우 컴퓨터의 메모리(데이터 저장소)를 많이 잡아먹는 경향이 있다.
방법론
편집- 브루트 포스: 그냥 알고리즘에 들어갈 수 있는 데이터의 경우의 수를 모조리 알고리즘대로 연산하여 특정한 결과를 만든 초기 데이터를 찾는 방법이다. 일반적으로 비효율적으로 여겨지며, 오랜 시간이 걸린다.
- 분할 정복: 어떤 문제를 그와 닮은 꼴의 작은 문제들로 나누어 쉽게 계산한 뒤 그 결과를 합치는 방법론이다.
- 그리디 알고리즘: 특정한 결과 값에 근접한 가장 큰 단위 데이터를 연쇄적으로 선택하는 알고리즘들을 통칭한다. 최소 신장 트리를 구성하는 방법이 대표적이다.
- 동적 계획법: 메모이제이션을 통해 이전에 연산한 결과를 기억하다가 다음 연산에 재투입하는 방법론. 공간 복잡도를 희생하여 시간 복잡도를 줄이는 데에 쓰인다.
TMI
편집- 확률을 사용하여 정답과 일치하거나 그에 근접한 답을 내는 근사 알고리즘도 존재할 수 있다. 50% 적중률을 넘기면 의미 있는 알고리즘으로 여겨진다.
참고 서적
편집- Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, "Algorithms"(McGRAW-HILL International Edition), McGRAW-HILL Education