알고리즘 사고 입문
서론
문제를 어떻게 효율적으로 해결할까? 같은 문제라도 어떤 사람이 쓴 코드는 몇 초 만에 결과가 나오고, 어떤 사람의 코드는 몇 분이 지나도 여전히 실행 중인 경우를 겪어보셨을 것입니다. 그 차이는 바로 알고리즘에 있습니다. 이 장에서는 알고리즘의 핵심 사고방식을 이해해 봅니다.
이 글에서 무엇을 배우게 되나요?
이 장을 마치면 다음을 얻게 됩니다:
- 문제 분해 능력: 복잡한 문제에 직면했을 때 분할 정복, 재귀 등의 전략으로 분해할 수 있고, 바로 코딩에 들어가지 않게 됩니다
- 효율성 판단 능력: 빅오 표기법으로 두 해법 중 어느 것이 더 효율적인지 감이 아닌 근거로 판단할 수 있습니다
- 복잡도 사고: 코딩 전에 데이터 규모와 시간 요구사항을 추정하고 적절한 알고리즘 수준을 선택합니다
- 후속 학습 기초: 고급 자료구조, 분산 시스템, 머신러닝을 위한 기반을 다집니다
| 장 | 내용 | 핵심 개념 |
|---|---|---|
| 제1장 | 이진 탐색 | 분할 정복 사고, O(log n) |
| 제2장 | 정렬 알고리즘 | 버블, 퀵, 병합 |
| 제3장 | 복잡도 분석 | 시간 복잡도, 공간 복잡도 |
0. 전경도: 알고리즘이란 무엇인가?
사전에서 단어를 찾는다고 상상해 봅시다:
- 방법 1: 첫 페이지부터 한 장씩 넘기며 찾기 (선형 탐색)
- 방법 2: 첫 글자로 위치를 파악한 뒤 이진 탐색 (이진 탐색)
두 방법 모두 찾을 수 있지만, 효율성은 천지 차이입니다. 알고리즘은 문제를 해결하는 방법입니다.
알고리즘의 핵심 지표:
| 지표 | 의미 | 왜 중요한가 |
|---|---|---|
| 시간 복잡도 | 데이터량 증가에 따른 실행 시간의 변화 추세 | 대규모 데이터의 성능 예측 |
| 공간 복잡도 | 데이터량 증가에 따른 메모리 사용량의 변화 추세 | 메모리 소비 평가 |
| 정확성 | 항상 올바른 결과를 내는지 여부 | 알고리즘의 기본 요구사항 |
📊 표 한 줄씩 읽기
시간 복잡도: 빅오 표기법으로 표현합니다. O(n)은 데이터량이 두 배가 되면 시간도 두 배가 된다는 뜻이고, O(n²)은 데이터량이 두 배가 되면 시간이 4배가 된다는 뜻입니다.
공간 복잡도: 마찬가지로 빅오 표기법을 사용합니다. 어떤 알고리즘은 공간을 희생하여 시간을 얻고(예: 해시 테이블), 어떤 알고리즘은 시간을 희생하여 공간을 얻습니다(예: 압축 알고리즘).
정확성: 알고리즘은 모든 가능한 입력에 대해 올바른 결과를 내야 합니다. 경계 조건(빈 입력, 극단적으로 큰 입력)에서 가장 오류가 발생하기 쉽습니다.
1. 이진 탐색: 매번 절반을 제외하기
1.1 이진 탐색의 원리
💡 이진 탐색은 어떻게 작동하나요?
전제 조건: 데이터가 정렬되어 있어야 합니다
과정:
- 중간 요소를 찾습니다
- 중간 요소가 대상과 같으면 찾았습니다!
- 대상이 중간 요소보다 작으면 왼쪽 절반에서 계속합니다
- 대상이 중간 요소보다 크면 오른쪽 절반에서 계속합니다
- 찾거나 존재하지 않음을 확인할 때까지 매번 절반을 제외합니다
시간 복잡도: O(log n)
생활 비유: 숫자 맞추기 게임. 1~100 사이의 숫자를 생각하고, 매번 중간값을 추측하면 큰지 작은지 알려줍니다. 최대 7번이면 맞출 수 있습니다(2⁷ = 128 > 100이므로).
👇 직접 해보기: 아래 데모는 이진 탐색의 작동 원리를 보여줍니다. 순차 탐색과 이진 탐색을 선택하여 비교해 보세요:
| Data size | Linear search | Binary search |
|---|---|---|
| 10 | At most 10 steps | At most 4 steps |
| 100 | At most 100 steps | At most 7 steps |
| 1000 | At most 1000 steps | At most 10 steps |
| 10000 | At most 10000 steps | At most 14 steps |
1.2 왜 이진 탐색이 이렇게 빠른가?
| 데이터량 | 선형 탐색 | 이진 탐색 |
|---|---|---|
| 100 | 100회 | 7회 |
| 1,000 | 1,000회 | 10회 |
| 1,000,000 | 1,000,000회 | 20회 |
| 1,000,000,000 | 1,000,000,000회 | 30회 |
📊 표 한 줄씩 읽기
첫 번째 열(데이터량): 검색할 데이터가 얼마나 되는지입니다. 데이터량이 100에서 10억으로 증가합니다(1000만 배 증가!)
두 번째 열(선형 탐색): 가장 "단순한" 방법으로, 첫 번째부터 하나씩 찾습니다. 검색 횟수는 데이터량과 같으며, 데이터가 많을수록 검색 횟수도 많아집니다.
세 번째 열(이진 탐색): 똑똑한 방법으로, 매번 절반을 제외합니다. 검색 횟수는 데이터량의 로그와만 관련이 있으며, 10억 개의 데이터도 단 30회면 됩니다!
비교 결론: 데이터량이 100만에 달하면 선형 탐색은 100만 회가 필요하지만, 이진 탐색은 20회면 충분합니다 — 5만 배의 차이입니다!
📊 로그 성장의 위력
이진 탐색의 시간 복잡도는 O(log n)으로, 다음을 의미합니다:
- 10억 개의 데이터, 최대 30회 검색
- 1조 개의 데이터, 최대 40회 검색
이것이 로그 성장의 위력입니다 — 데이터량이 1000배 증가해도 검색 횟수는 10회만 증가합니다.
2. 정렬: 무질서를 질서로
2.1 일반적인 정렬 알고리즘
| 알고리즘 | 시간 복잡도 | 특징 | 적용 시나리오 |
|---|---|---|---|
| 버블 정렬 | O(n²) | 단순하지만 느림 | 교육용, 소량 데이터 |
| 선택 정렬 | O(n²) | 단순하지만 느림 | 소량 데이터 |
| 삽입 정렬 | O(n²) | 거의 정렬된 데이터에 빠름 | 소량 데이터, 거의 정렬됨 |
| 퀵 정렬 | O(n log n) | 실제로 가장 빠름 | 범용 정렬 |
| 병합 정렬 | O(n log n) | 안정 정렬 | 안정성이 필요한 시나리오 |
| 힙 정렬 | O(n log n) | 제자리 정렬 | 메모리 제한 시나리오 |
📊 표 한 줄씩 읽기
버블 정렬: 가장 기본적인 정렬 알고리즘으로, 물속의 거품이 위로 올라가는 것과 같습니다. 이해하기 쉽지만 속도가 가장 느립니다. 정렬 개념을 배우기에 적합하지만 실제 사용에는 부적합합니다.
선택 정렬: 매번 가장 작은 것을 골라 앞에 놓습니다. 역시 단순하지만, 데이터가 정렬되어 있는지와 관계없이 같은 양의 비교를 수행합니다.
삽입 정렬: 트럼프 카드를 정리하는 것과 같습니다. 각 요소를 앞쪽 이미 정렬된 부분에 삽입합니다. 거의 정렬된 데이터에 매우 효율적입니다.
퀵 정렬: 실제 개발에서 가장 자주 사용되는 정렬입니다. 평균적으로 가장 빠르지만, 최악의 경우(이미 정렬된 데이터)에는 O(n²)로 저하됩니다.
병합 정렬: "분할 정복" 사상을 채택하여 항상 O(n log n)이지만 추가 공간이 필요합니다. 안정 정렬이 필요한 시나리오에 적합합니다.
힙 정렬: 힙이라는 자료구조를 이용한 정렬로, 제자리 정렬(추가 공간 불필요)이지만 실제 실행 속도는 퀵 정렬보다 느린 경우가 많습니다.
2.2 왜 퀵 정렬이 "빠른가"?
💡 퀵 정렬의 원리
핵심 사상: 분할 정복법
- "기준(pivot)" 요소를 하나 선택합니다
- 기준보다 작은 것은 왼쪽에, 큰 것은 오른쪽에 놓습니다
- 왼쪽과 오른쪽 부분을 각각 재귀적으로 정렬합니다
- 결과를 병합합니다
왜 빠른가?
- 매번 분할 후 기준 요소는 최종 위치에 놓입니다
- 평균적으로 매번 분할 시 약 절반의 요소를 제외합니다
- 시간 복잡도 O(n log n)
생활 비유: 책장 정리. 책 한 권을 꺼내 그것보다 얇은 것은 왼쪽에, 두꺼운 것은 오른쪽에 놓습니다. 그런 다음 왼쪽과 오른쪽 더미 각각에 이 과정을 반복합니다.
👇 직접 해보기: 아래 데모는 정렬 알고리즘의 시각화를 보여줍니다. 배열을 생성하고 버블 정렬과 퀵 정렬의 과정을 비교해 보세요:
| Algorithm | Average time | Worst time | Space | Stable |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(n²) | O(1) | ✓ |
| Quick sort | O(n log n) | O(n²) | O(log n) | ✗ |
| Merge sort | O(n log n) | O(n log n) | O(n) | ✓ |
| Insertion sort | O(n²) | O(n²) | O(1) | ✓ |
3. 재귀: 자기 자신을 호출하기
3.1 재귀의 본질
💡 재귀란 무엇인가?
재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다.
두 가지 핵심 요소:
- 기본 경우(Base case): 언제 재귀를 멈출 것인가?
- 재귀 단계: 문제를 더 작은 하위 문제로 어떻게 분해할 것인가?
고전적인 예: 팩토리얼
function factorial(n) {
if (n <= 1) return 1 // 기본 경우
return n * factorial(n - 1) // 재귀 단계
}생활 비유: 러시아 인형. 하나를 열면 더 작은 인형이 나오고, 가장 작은 것은 열 수 없을 때까지 계속됩니다.
3.2 재귀 vs 반복
| 특성 | 재귀 | 반복(루프) |
|---|---|---|
| 코드 간결성 | 일반적으로 더 간결 | 더 복잡할 수 있음 |
| 메모리 소비 | 높음(호출 스택) | 낮음 |
| 성능 | 약간 느림(함수 호출 오버헤드) | 더 빠름 |
| 적용 시나리오 | 트리 순회, 분할 정복 알고리즘 | 단순 반복 작업 |
📊 표 한 줄씩 읽기
코드 간결성: 재귀는 일반적으로 몇 줄의 코드로 복잡한 로직을 표현할 수 있지만(예: 트리 구조 순회), 루프를 사용하면 더 많은 변수와 중첩이 필요할 수 있습니다.
메모리 소비: 재귀는 "호출 스택"을 사용하여 각 레벨의 정보를 저장합니다. 접시를 쌓는 것과 같아서, 재귀가 한 단계 깊어질 때마다 접시가 하나 더 추가됩니다. 루프는 이러한 오버헤드가 없습니다.
성능: 함수 호출마다 오버헤드가 있으므로(매개변수 전달, 스택 조작 등) 재귀는 일반적으로 루프보다 약간 느립니다.
적용 시나리오: 재귀는 본질적으로 재귀적인 구조의 문제(예: 파일 트리, DOM 트리)에 적합하고, 루프는 단순한 반복 작업(예: 배열 순회)에 적합합니다.
⚠️ 재귀의 함정
스택 오버플로우: 재귀 깊이가 너무 깊어 호출 스택 공간이 고갈됩니다.
해결 방법:
- 반복으로 변경
- 꼬리 재귀 최적화 사용(일부 언어에서 지원)
- 재귀 깊이 제한
👇 직접 해보기: 아래 데모는 재귀의 호출 과정을 보여줍니다. 함수가 어떻게 자기 자신을 호출하는지 관찰해 보세요:
Open that one and there is an even smaller one, until the smallest case
That is recursion.
- Concise code
- Naturally expresses recursive structures
- Good for tree and graph traversal
- May repeat work
- Uses stack space
- Can be harder to debug
4. 탐욕 알고리즘: 매 단계에서 최적 선택하기
4.1 탐욕적 사고
💡 탐욕 알고리즘이란 무엇인가?
탐욕 알고리즘은 매 단계에서 현재 가장 최적으로 보이는 선택을 하여 최종적으로 전역 최적해를 얻고자 합니다.
적용 조건:
- 탐욕적 선택 성질: 지역 최적이 전역 최적으로 이어짐
- 최적 부분 구조: 문제의 최적해가 하위 문제의 최적해를 포함함
고전적인 예: 동전 거스름돈
- 목표: 가장 적은 동전으로 지정된 금액 만들기
- 탐욕 전략: 매번 가장 큰 동전 선택
- 결과: 67위안 = 50 + 10 + 5 + 1 + 1 (5개)
생활 비유: 등산할 때 매번 가장 가파른 길을 선택해 올라갑니다. 반드시 가장 높은 봉우리에 도달하는 것은 아니지만, 보통 괜찮은 위치에 도달할 수 있습니다.
4.2 탐욕의 한계
⚠️ 탐욕이 항상 최적해를 보장하지는 않음
반례: 동전 거스름돈
동전 액면이 [1, 3, 4]이고 6위안을 만들어야 한다면:
- 탐욕: 4 + 1 + 1 = 3개
- 최적: 3 + 3 = 2개
탐욕 알고리즘이 여기서 실패했습니다!
교훈: 탐욕 알고리즘은 단순하고 효율적이지만 항상 최적해를 얻을 수 있는 것은 아닙니다. 사용하기 전에 문제가 탐욕 조건을 만족하는지 증명해야 합니다.
👇 직접 해보기: 아래 데모는 탐욕 알고리즘의 실제 효과를 보여줍니다. 다양한 동전 조합을 시도하고 탐욕 전략의 성능을 관찰해 보세요:
It hopes a series of local choices reaches a global optimum
✓ Works for currencies such as RMB and USD
| Feature | Greedy algorithm | Dynamic programming |
|---|---|---|
| Decision style | Choose the current best each step | Consider all possibilities and choose the best |
| Optimality | May not be globally optimal | Guarantees a global optimum |
| Time complexity | O(n) or O(n log n) | O(n²) or higher |
| Best fit | Local optimum → global optimum | Overlapping subproblems |
- Simple to implement
- Efficient
- Low space complexity
- Does not always guarantee a global optimum
- Limited applicability
- Requires an optimality proof
5. 알고리즘 설계 패러다임
| 패러다임 | 사상 | 대표 알고리즘 | 적용 문제 |
|---|---|---|---|
| 분할 정복 | 문제를 작은 문제로 분해 | 퀵 정렬, 병합 정렬 | 분해 가능한 문제 |
| 탐욕 | 매 단계에서 최적 선택 | 최소 신장 트리, 허프만 코딩 | 탐욕적 성질이 있는 문제 |
| 동적 계획법 | 하위 문제의 해를 기록 | 배낭 문제, 최단 경로 | 중복되는 하위 문제 |
| 백트래킹 | 시도하고, 안 되면 되돌아가기 | N-퀸, 전체 순열 | 탐색 문제 |
📊 표 한 줄씩 읽기
분할 정복: 큰 문제를 작은 문제로 나누어 각각 해결한 후 병합합니다. 방 청소와 같아서, 거실, 침실, 주방으로 나누어 각각 청소하고 마지막에 전체적으로 깨끗해집니다.
탐욕: 매번 현재 가장 좋은 것을 선택하고 장기적 결과를 고려하지 않습니다. 식사할 때 가장 좋아하는 반찬부터 먹는 것과 같아서, 최적의 식사 방법이 아닐 수 있지만 속도가 빠릅니다.
동적 계획법: 중간 결과를 기억하여 중복 계산을 피합니다. 메모하는 것과 같아서, 다음에 같은 문제를 만나면 바로 답을 찾고 다시 풀 필요가 없습니다.
백트래킹: 막히면 되돌아가서 다시 시도합니다. 미로 찾기와 같아서, 이 길이 막히면 이전 교차로로 돌아가 다른 길을 시도합니다.
👇 직접 해보기: 아래 데모는 다양한 알고리즘 설계 패러다임의 특징과 적용 시나리오를 보여줍니다:
| Paradigm | Core strategy | Optimality | Use case |
|---|---|---|---|
| ✂️ Divide and conquer | Split → recurse → combine | Guarantees optimum | Problems that split independently |
| 📊 Dynamic programming | Store subproblem answers | Guarantees optimum | Overlapping subproblems |
| 🎯 Greedy | Choose the best each time | Not always optimal | Local optimum → global optimum |
| 🔙 Backtracking | Depth-first search | Guarantees optimum | Small search spaces that need enumeration |
6. 요약: 알고리즘은 문제 해결의 예술
여러 알고리즘 사상을 하나의 비유로 요약해 봅시다:
| 사상 | 비유 | 핵심 요점 |
|---|---|---|
| 이진 탐색 | 숫자 맞추기 | 매번 절반 제외 |
| 정렬 | 책장 정리 | 질서 세우기 |
| 재귀 | 러시아 인형 | 큰 것을 작게 만들기 |
| 탐욕 | 등산 시 경로 선택 | 지역 최적 |
💡 핵심 통찰
알고리즘의 본질은 "효율성"과 "정확성"의 균형입니다.
- 좋은 알고리즘은 프로그램의 효율성을 몇 자릿수 향상시킬 수 있습니다
- 하지만 과도한 최적화는 복잡성을 도입할 수 있습니다
- 먼저 정확성을 보장하고, 그 다음 효율성을 추구하세요
특정 알고리즘을 암기하는 것보다 알고리즘적 사고를 이해하는 것이 더 중요합니다:
- 분할 정복: 큰 문제를 작은 문제로 분해
- 탐욕: 매 단계에서 최적 선택
- 동적 계획법: 하위 문제의 해를 기록
- 백트래킹: 시도하고, 막히면 되돌아가기
추가 읽기
- 알고리즘 입문: 알고리즘을 체계적으로 학습하는 고전 교재
- LeetCode: 문제 풀이로 알고리즘 능력 향상
- 알고리즘 시각화: 알고리즘 실행 과정을 직관적으로 이해
- 경쟁 알고리즘: 더 고급 알고리즘 기법 학습