한 문제, 여러 가지 알고리즘
알고리즘은 문제를 풀기 위한 정확한 단계들의 모음이에요. 대부분의 문제는 알고리즘이 하나가 아니에요. 예를 들어 목록에서 이름을 찾을 때, 모든 이름을 하나씩 확인할 수도 있고, 목록이 정렬되어 있다면 계속 반으로 나눌 수도 있어요.
두 방법 모두 정답을 줘요. 차이는 효율성, 즉 작업량과 메모리가 얼마나 드는지예요. 좋은 프로그래머는 데이터가 커져도 빠른 알고리즘을 골라요.
걸린 시간으로 알고리즘 비교하기
초시계로 재는 것은 공정하지 않아요. 빠른 컴퓨터에서는 느린 알고리즘도 빨라 보이니까요. 그래서 입력 크기 n에 따라 기본 단계(비교, 교환, 덧셈)가 몇 번인지 세요.
최선, 평균, 최악의 경우
최선의 경우는 가장 운이 좋은 입력이에요(13이 첫 번째 상자에 있으면 1단계). 최악의 경우는 가장 운이 나쁜 입력이에요(13이 없으면 n단계). 보통 최악의 경우를 말해요. 그것이 약속이기 때문이에요. 알고리즘은 이보다 더 느려지지 않아요.
시간 복잡도와 공간 복잡도
시간 복잡도는 n에 따라 단계 수가 어떻게 늘어나는지 알려 줘요. 공간 복잡도는 n에 따라 추가 메모리가 어떻게 늘어나는지 알려 줘요. 병합 정렬은 빠르지만 추가 메모리가 필요하고, 버블 정렬은 추가 메모리가 거의 필요 없지만 느려요.
빅오 표기법
빅오는 작은 부분은 무시하고 증가 속도만 나타내요. 가장 큰 항만 남기고 상수는 버려요. 3n² + 5n + 2는 O(n²)가 돼요. n이 크면 n² 부분이 거의 전부이기 때문이에요.
| 빅오 | 이름 | n = 16 | n = 1000 | 예 |
|---|---|---|---|---|
| O(1) | 상수 | 1 | 1 | 배열의 5번째 항목 읽기 |
| O(log n) | 로그 | 4 | 약 10 | 이진 탐색 |
| O(n) | 선형 | 16 | 1000 | 선형 탐색, 가장 큰 값 찾기 |
| O(n log n) | n log n | 64 | 약 10,000 | 병합 정렬 |
| O(n²) | 이차 | 256 | 1,000,000 | 버블 정렬, 중첩 반복문 |
코드에서 쓰는 간단한 규칙: n개를 도는 반복문 하나는 O(n), 반복문 안의 반복문은 O(n²), 매번 문제를 반으로 줄이면 O(log n)이에요.
선형 탐색과 이진 탐색의 효율
선형 탐색은 항목을 하나씩 확인해요. 최악의 경우 비교가 n번이라서 O(n)이에요. 정렬되어 있든 아니든 어떤 목록에도 쓸 수 있어요.
이진 탐색은 정렬된 목록이 필요해요. 가운데를 보고, 너무 크면 오른쪽 절반을, 아니면 왼쪽 절반을 버려요. 한 단계마다 목록이 반으로 줄어서 최악의 경우 비교는 약 log₂ n + 1번, 즉 O(log n)이에요. 항목이 1,000,000개여도 1,000,000단계가 아니라 약 20단계면 돼요.
정렬 알고리즘의 효율
버블, 삽입, 선택 정렬은 반복문 안에 반복문이 있어서 비교가 약 n²/2번, 즉 O(n²)이에요. 삽입 정렬은 이미 정렬된 목록이라는 최선의 경우에는 O(n)이에요.
병합 정렬은 목록을 약 log₂ n번 반으로 나누고, 각 층에서 약 n만큼 일해요. 그래서 O(n log n)이고, 추가 메모리 O(n)이 필요해요.
이진 탐색은 정렬된 목록이 필요해요. 한 번만 찾는다면 먼저 정렬하는 비용(n log n)이 선형 탐색 한 번(n)보다 커요. 여러 번 찾는다면 한 번 정렬해 두는 것이 이득이에요.
사전 조건, 사후 조건, 재귀의 함정
사전 조건은 알고리즘을 시작하기 전에 참이어야 하는 것이에요(이진 탐색: 목록이 정렬되어 있음). 사후 조건은 끝났을 때 보장되는 것이에요(정렬: 모든 항목이 다음 항목보다 작거나 같음). 이것을 적어 두면 알고리즘을 테스트하고 증명하기 쉬워요.
재귀는 함수가 더 작은 문제에 대해 자기 자신을 부르는 것이에요. 자주 하는 실수:
- 종료 조건(기저 사례)이 없거나, 절대 도달하지 못해요. 호출이 끝나지 않아요(스택 오버플로).
- 호출할 때마다 문제가 작아지지 않아요.
- 같은 일을 반복해요. 단순한 재귀 피보나치는 fib(3)을 계속 다시 계산해서 O(2ⁿ)처럼 늘어나요. 답을 저장해 두면(메모이제이션) O(n)이 돼요.
- 재귀가 매우 깊으면 호출마다 스택 프레임이 하나씩 쌓여 메모리를 많이 써요.
해 보기: 두 탐색 경주시키기
종이 쪽지에 1부터 32까지 숫자를 적고, 순서대로 뒤집어 놓아요. 친구에게 비밀 숫자 하나를 고르게 해요. 먼저 하나씩 뒤집으며 몇 장을 뒤집었는지 세요. 그다음에는 항상 가운데 쪽지를 뒤집으며 찾아요. 5번 반복해 보세요. 어떤 방법이 6번을 넘기지 않았나요? 마지막 3D 단계의 슬라이더로 확인해 보세요(n = 32: log₂ 32 = 5).
핵심 공식과 정의
- 선형 탐색: 최악의 경우 비교 n번 → O(n)
- 이진 탐색: 최악의 경우 비교 약 log₂ n + 1번 → O(log n)
- 버블 / 삽입 / 선택 정렬: 비교 약 n(n − 1)/2번 → O(n²)
- 병합 정렬: 비교 약 n log₂ n번 → O(n log n)
- 빅오 규칙: 가장 큰 항만 남기고 상수는 버리기 (5n² + 3n → O(n²))
- n을 두 배로: O(1) 그대로, O(log n) +1, O(n) ×2, O(n²) ×4
풀이 예제
1. 목록에 이름이 50개 있어요. 선형 탐색은 최선과 최악의 경우 비교가 몇 번 필요할까요?
최선의 경우: 이름이 맨 앞에 있으면 비교 1번. 최악의 경우: 이름이 맨 끝에 있거나 없으면 비교 50번. 선형 탐색은 O(n)이에요.
2. 정렬된 항목 1024개에서 이진 탐색이 필요로 하는 비교는 최대 몇 번일까요?
한 단계마다 목록이 반으로 줄어요: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. 반으로 나누기가 10번이고, 마지막 확인까지 하면 최대 11번 비교해요(log₂ 1024 = 10).
3. f(n) = 4n² + 10n + 7의 빅오를 구하세요.
가장 큰 항(4n²)만 남기고 상수 4를 버려요: O(n²).
4. 반복문이 i를 1부터 n까지 돌고, 그 안에서 또 다른 반복문이 j를 1부터 n까지 돌아요. 안쪽 줄은 몇 번 실행될까요?
i의 n개 값마다 n번씩이니까 n × n = n²번이에요. 시간 복잡도는 O(n²).
5. O(n²) 프로그램이 1000개를 정렬하는 데 2초 걸려요. 3000개는 대략 얼마나 걸릴까요?
n이 3배가 되면 n²은 3² = 9배가 돼요. 약 2 × 9 = 18초예요.
6. n = 1000개일 때 버블 정렬과 병합 정렬을 비교하세요.
버블 정렬: 약 n²/2 = 500,000번 비교. 병합 정렬: 약 n log₂ n = 1000 × 10 = 10,000번. 병합 정렬은 일이 약 50배 적지만 추가 메모리가 필요해요.
자주 하는 실수
- 컴퓨터 한 대에서 초시계로만 속도를 재는 것. 대신 n에 따른 단계 수를 세세요.
- 정렬되지 않은 목록에 이진 탐색을 쓰는 것. 이진 탐색의 사전 조건은 정렬된 목록이에요.
- 빅오에 상수를 남기는 것, 예를 들어 O(2n)이라고 쓰는 것. 그냥 O(n)이에요.
- 종료 조건이 없거나 문제를 작게 만들지 못하는 재귀 함수를 쓰는 것.