[알고리즘] 01_알고리즘 개요와 복잡도
같은 문제를 푸는 방법은 여러 가지고, 그중에는 빠른 것도 느린 것도 있다. 알고리즘은 "문제를 푸는 절차"를 다루고, 그 절차가 얼마나 효율적인지를 따지는 게 복잡도다. 오늘은 알고리즘이 갖춰야 할 조건부터 성능을 재는 빅오 표기법까지, 알고리즘 공부의 토대를 잡았다.
1. 알고리즘의 정의와 요건
어떤 문제를 해결하기 위한 일련의 순서(명령어의 나열)다. 가장 오래된 알고리즘으로는 기원전 300년경 유클리드의 최대공약수 알고리즘이 꼽힌다.
알고리즘이라 부르려면 다음 다섯 조건을 갖춰야 한다.
| 요건 | 설명 |
|---|---|
| 입력(Input) | 0개 이상의 외부 입력 |
| 출력(Output) | 1개 이상의 출력 |
| 정확성 | 주어진 입력에 대해 올바른 해를 냄 |
| 유한성 | 일정 시간 안에 반드시 종료 |
| 수행성 | 모든 명령이 실제로 실행 가능 |
입력은 없어도(0개) 되지만 출력은 반드시 하나 이상 있어야 한다는 점, 그리고 유한성(언젠가는 끝나야 함)이 특히 중요했다. 끝나지 않는 절차는 알고리즘이 아니다. 무한 루프가 알고리즘이 못 되는 이유가 이 유한성 조건에 있었다.
2. 알고리즘의 표현
알고리즘은 코드로 옮기기 전에 사람이 이해할 형태로 표현한다.
- 자연어: 사람의 말. 직관적이지만 모호할 수 있다.
- 의사코드(Pseudocode): 프로그램과 자연어의 중간. 특정 언어 문법에 매이지 않아 핵심 논리만 표현한다.
- 순서도(Flowchart): 기호와 도형으로 처리 흐름을 그림으로 나타낸다.
그리고 모든 알고리즘은 순차·선택·반복이라는 세 가지 기본 구조의 조합으로 만들어진다. 차례로 실행하고(순차), 조건에 따라 갈라지고(선택), 반복하는(반복) 것이 전부다.
3. 복잡도와 성능 분석
알고리즘의 효율은 두 가지로 잰다.
| 종류 | 의미 |
|---|---|
| 시간 복잡도 | 필요한 연산 횟수 (얼마나 빠른가) |
| 공간 복잡도 | 필요한 메모리 양 (얼마나 적게 쓰는가) |
실제 수행 시간은 컴퓨터 성능에 따라 들쭉날쭉하다. 같은 알고리즘도 빠른 PC에선 빠르고 느린 PC에선 느리다. 그래서 하드웨어와 무관하게 "입력 크기에 따라 연산을 몇 번 하는가"로 효율을 측정한다. 보통 둘 중 시간 복잡도를 더 중요하게 본다.
처음엔 "그냥 시간을 재면 되지" 싶었는데, PC마다 결과가 달라진다는 점을 생각하니 연산 횟수로 재는 이유가 납득됐다.
성능은 최선·평균·최악으로 나눠 볼 수 있는데, 알고리즘 평가에는 보통 최악의 경우(Worst Case)를 쓴다. "아무리 나빠도 이만큼은 보장한다"가 가장 안전한 기준이기 때문이다.
4. 빅오(Big-O) 표기법
시간 복잡도를 나타내는 표기법으로, 최악의 경우를 기준으로 입력이 커질 때 연산이 늘어나는 정도를 나타낸다. 가장 빠르게 증가하는 항(최고차항)만 남기고 계수와 낮은 차수 항은 무시한다.
T(n) = 2n → O(n)
T(n) = ½n² + 3n → O(n²)
T(n) = 3n² + 5n + 2 → O(n²)
입력이 충분히 커지면 최고차항이 전체를 지배하므로, 나머지는 무시해도 경향이 같기 때문이다. 자주 보는 복잡도를 느린 순으로 늘어놓으면 이렇다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
이 순서를 머리에 넣어두면, 어떤 알고리즘이 "쓸 만한지" 한눈에 가늠할 수 있다. 예를 들어 O(n²)와 O(n log n)은 데이터가 커질수록 엄청난 속도 차이를 낸다. 계수와 낮은 항을 버린다는 게 처음엔 부정확해 보였는데, "입력이 커지면 최고차항이 지배한다"를 받아들이니 왜 그렇게 단순화하는지 이해됐다.
5. 예제로 보는 연산 횟수
복잡도는 공식을 외우는 것보다 "코드가 몇 번 도는가"를 세어보는 편이 이해가 빠르다. 다음은 1부터 n까지의 합을 반복으로 구하는 C 코드다.
int iNo;
int iIndex;
int iSum;
printf("정수 입력: ");
scanf("%d", &iNo);
iSum = 0;
for (iIndex = 0; iIndex < iNo; iIndex++)
{
iSum = iSum + (iIndex + 1);
}
printf("합계: %d\n", iSum);
반복문은 iNo번 돈다. 입력이 10이면 10번, 100이면 100번이다. 그래서 시간복잡도는 O(n)이다.
| 입력 n | 반복 횟수 | 복잡도 관점 |
|---|---|---|
| 10 | 10 | n에 비례 |
| 100 | 100 | n에 비례 |
| 1000 | 1000 | n에 비례 |
같은 문제를 이중 반복으로 잘못 풀면 바깥 반복 n번, 안쪽 반복 n번이 곱해져 O(n²)가 된다.
int iNo;
int iOuter;
int iInner;
int iCount;
printf("정수 입력: ");
scanf("%d", &iNo);
iCount = 0;
for (iOuter = 0; iOuter < iNo; iOuter++)
{
for (iInner = 0; iInner < iNo; iInner++)
{
iCount = iCount + 1;
}
}
printf("반복 횟수: %d\n", iCount);유제: 복잡도 직접 세기
- 위 이중 반복에서
iInner < iOuter + 1로 조건을 바꾸면 총 반복 횟수는 어떻게 변하는가? - 배열 n개에서 최댓값을 찾는 코드는 왜
O(n)인지 설명하라. - 배열 n개에서 모든 두 원소 쌍을 비교하는 코드는 왜
O(n²)인지 표로 정리하라.
오늘 느낀 점
- 알고리즘의 다섯 요건 중 유한성·출력이 왜 강조되는지, 무한 루프나 출력 없는 절차를 떠올리니 자연히 납득됐다. 정의를 외우기보다 반례로 이해하는 게 빨랐다.
- "연산 횟수로 효율을 잰다"는 발상이 하드웨어 의존성을 없애기 위한 거라는 걸 알고, 빅오가 추상적인 게 아니라 실용적 약속이라는 게 보였다.
- 복잡도 순서표 하나로 알고리즘의 쓸모를 가늠할 수 있다는 게 든든했다. 앞으로 배울 정렬·탐색을 이 잣대로 비교하면 되겠다.
한 걸음 더
- 빅오가 "상한(최악)"이라면, 하한을 나타내는 빅오메가(Ω), 상·하한이 같은 경우를 나타내는 빅세타(Θ)도 있다. 실무에선 대개 빅오만 쓰지만, 엄밀히는 세 가지로 알고리즘의 성능 범위를 감싼다.
- 같은 빅오라도 실제 속도는 다를 수 있다. O(n) 알고리즘이라도 상수 계수가 크면, 작은 입력에선 O(n²)보다 느릴 수 있다. 빅오는 "입력이 충분히 클 때의 경향"을 보는 것이라, 작은 데이터에선 그 경향이 잘 안 드러난다는 점을 기억해야 한다.
- P와 NP는 알고리즘 이론의 유명한 난제다. 다항식 시간(O(n³) 이하 등)에 풀리는 문제를 P, 답을 빠르게 검증은 하지만 빠르게 풀 방법을 모르는 문제를 NP라 한다. "P = NP인가?"는 아직 증명되지 않은 컴퓨터과학 최대 난제로, 일반적으로 P ≠ NP일 거라 추측한다. 암호 체계의 안전성도 이 가정 위에 서 있다.