[공부][알고리즘] 알고리즘 기본 개념 정리

컴퓨터 알고리즘이란 컴퓨터를 사용하여 문제를 해결하기 위한 단계적인 방법이다.

문제를 해결할 때는 문제 정의, 전략 수립, 알고리즘 설계, 분석(정확성, 시공간 복잡도, 최적성), 구현, 검증의 단계를 거친다.

 

이 글에서는 작성한 알고리즘을 어떻게 분석하고 평가하는지 핵심 개념을 정리해 보겠다.

1. 알고리즘 분석의 기준

알고리즘을 분석하는 이유는 더 나은 알고리즘으로 개선하거나, 여러 방법 중 가장 적합한 것을 선택하기 위해서다.

주요 분석 기준은 다음과 같다.

• 정확성 (Correctness): 입력이 주어졌을 때 의도한 출력이 나오는지 증명해야 한다. 알고리즘이 종료될 때 사전 조건이 만족되면 사후 조건도 참이 됨을 증명하는 과정이다.
• 수행 시간과 공간 (Amount of work done, and space used): 컴퓨터나 언어에 독립적인 효율성 지표가 필요하다. 이를 위해 문제의 기본 연산(Basic Operation)을 정의하고, 이 연산이 수행되는 횟수를 측정한다.
• 최적성 (Optimality): 해당 문제를 해결하는 데 필요한 최소한의 작업량을 의미한다.

수행 시간을 분석할 때는 주로 두 가지 관점을 사용한다.

• 최악의 경우 (Worst-Case Complexity): 입력 크기 n에 대해 알고리즘이 수행하는 최대 기본 연산 횟수인 W(n)을 구한다.
• 평균의 경우 (Average Complexity): 각 입력이 발생할 확률을 고려하여 평균적인 수행 시간인 A(n)을 계산한다.

---

2. 점근적 증가율과 함수 분류

알고리즘의 성능은 상수 요인을 무시하고 입력 크기가 커질 때의 증가율로 분류한다.

• O(g) (Big-O): 알고리즘의 상한선을 의미한다. 최악의 경우에도 함수가 g보다 빠르게 증가하지 않음을 나타낸다.
• Ω(g) (Big-Omega): 알고리즘의 하한선을 의미한다. 최상의 경우라도 함수가 최소한 g만큼 빠르게 증가함을 나타낸다.
• Θ(g) (Big-Theta): 상한선과 하한선이 일치할 때 사용하며, 함수가 g와 같은 비율로 증가함을 의미한다.

극한을 사용하여 두 함수의 증가율을 비교할 수도 있다. n이 무한대로 갈 때 f(n)/g(n)의 극한값을 구해보면 다음과 같이 분류할 수 있다.

• 극한값이 0이면 o(g) (Little-o)
• 0보다 큰 상수면 Θ(g) (Big-Theta)
• 무한대면 ω(g) (Little-omega)

---

3. 배열 탐색을 통한 알고리즘 비교와 최적성 증명

정렬되지 않은 배열에서 특정 값을 찾는 순차 탐색(Sequential Search)의 경우, 최악의 상황에서는 모든 원소를 다 확인해야 하므로 W(n) = n 이다.

순차 탐색 문제 자체의 최소 필요 작업량(하한선)인 F(n) 역시 n이므로, 정렬되지 않은 배열에서는 순차 탐색이 최적인 알고리즘이다.

 

하지만 배열이 정렬되어 있다면 분할 정복 기법인 이진 탐색(Binary Search)을 사용할 수 있다.

배열의 중간값과 비교하여 탐색 범위를 절반씩 줄여나가므로, 최악의 경우 비교 횟수는 log(n+1)의 올림 값이 된다. 즉 Θ(log n) 의 복잡도를 가진다.

 

그렇다면 이진 탐색이 정렬된 배열 탐색에서 최선의 방법일까? 이를 증명하기 위해 결정 트리(Decision Tree)를 사용할 수 있다.

• 크기가 n인 배열을 탐색하는 올바른 알고리즘의 결정 트리는 최소한 n개의 노드(N)를 가져야 한다.
• 트리의 최대 깊이(비교 횟수)를 p라고 할 때, 노드의 총 개수는 2^p - 1을 넘을 수 없다.
• 즉, 2^p ≥ N + 1 ≥ n + 1 이 성립하므로, p ≥ log(n+1) 이라는 하한선이 도출된다.

이진 탐색의 최악의 경우 수행 시간과 문제의 하한선이 일치하므로, 이진 탐색은 수학적으로 증명된 최적(Optimal) 알고리즘이다.

---

알고리즘을 공부할 때는 단순히 코드를 짜는 것을 넘어 이 알고리즘이 수학적으로 얼마나 효율적이고 최적인지를 증명하는 과정이 필수적이다.

 

오늘 정리한 기초 증명 방식들을 잘 기억해 두면 앞으로 마주할 복잡한 알고리즘의 효율성을 평가하는 데 큰 도움이 될 것이다.