1. 5가지 알고리즘 큰 그림
이번 강에서 다룰 알고리즘들의 분류와 위치다.
| 검색 | 선형 검색 (Linear Search) | 처음부터 하나씩 |
| 검색 | 이진 검색 (Binary Search) | 절반씩 줄여나가기 |
| 정렬 | 버블 정렬 (Bubble Sort) | 인접 비교·교환 |
| 정렬 | 삽입 정렬 (Insertion Sort) | 카드 정리 방식 |
| 최적화 | 탐욕 알고리즘 (Greedy) | 매 순간 최선 선택 |
💡 현실 충격: 버블·삽입 정렬은 실무에서 절대 쓰지 않는다. 학습용으로만 의미가 있다. 진짜 정렬은 퀵소트, 머지소트, 팀소트 같은 더 빠른 알고리즘을 사용한다. 하지만 기본 정렬 원리를 이해하지 못하면 고급 정렬도 이해할 수 없다.
2. 선형 검색 (Linear Search) ⭐
정의
리스트의 첫 번째 원소부터 차례대로 하나씩 검색하여 원하는 값을 찾는 무식하지만 확실한 방법.
책 한 페이지씩 넘기기 비유
책에서 특정 단어를 찾을 때, 첫 페이지부터 한 줄씩 모두 읽는 방식. 단순하지만 시간이 오래 걸린다.
작동 원리 (4단계)
| 1 | 첫 번째 원소(i=1)부터 시작 |
| 2 | 현재 원소가 찾으려는 값 x와 같은지 확인 |
| 3 | 같지 않으면 다음 원소(i+1)로 이동, 반복 |
| 4 | x를 찾으면 인덱스 반환, 끝까지 못 찾으면 0 반환 |
의사코드
procedure linear search (x: integer, a₁, a₂, ..., aₙ: distinct integers)
i := 1
while (i ≤ n and x ≠ aᵢ)
i := i + 1
if i ≤ n then location := i
else location := 0
return location {index or 0 if not found}실행 추적 예제
수열: {3, 6, 9, 12, 15, 18, 21, 24}, 찾는 값: x = 12
| 1 | 1 | 3 | ❌ |
| 2 | 2 | 6 | ❌ |
| 3 | 3 | 9 | ❌ |
| 4 | 4 | 12 | ⭕ 찾음! |
→ 반환: 4 (12의 인덱스)
특징
| 장점 | 구현이 매우 단순 |
| 장점 | 정렬 여부 무관 (정렬 안 된 리스트에서도 작동) |
| 단점 | 리스트가 클수록 느려짐 |
| 최악 경우 | 모든 n개 원소 비교 → n번 비교 |
💡 시험 핵심: 선형 검색은 정렬 여부와 무관하다. 이는 다음에 배울 이진 검색과의 결정적 차이다.
3. 이진 검색 (Binary Search) ⭐⭐⭐
정의
정렬된 리스트에서 남은 탐색 구간의 중간 원소와 비교하여 탐색 구간을 절반으로 줄여나가는 효율적인 검색 방법.
사전 찾기 비유
사전에서 'machine'을 찾는다고 하자. 사전 중간을 펼쳐서 확인 → 'm'이 사전 중간 즈음에 있다면 그 부분만 보면 됨 → 그 안에서 또 절반씩 줄여나감.
이것이 이진 검색의 핵심 직관.
절대 조건 ⚠️
데이터가 반드시 정렬되어 있어야 한다.
정렬되지 않은 데이터에서는 이진 검색을 사용할 수 없다.
작동 원리 (5단계)
| 1 | 양 끝점 i (왼쪽), j (오른쪽) 설정 |
| 2 | 중간점 m = ⌊(i+j)/2⌋ 계산 |
| 3 | x와 aₘ 비교 |
| 4 | x > aₘ → 오른쪽 절반 (i = m+1), x < aₘ → 왼쪽 절반 (j = m), x = aₘ → 찾음! |
| 5 | 탐색 구간 없어질 때까지 반복 |
의사코드
procedure binary search (x: integer, a₁, a₂, ..., aₙ: distinct integers)
i := 1 {왼쪽 끝}
j := n {오른쪽 끝}
while i < j begin
m := ⌊(i+j)/2⌋ {중간점}
if x > aₘ then i := m+1 else j := m
end
if x = aᵢ then location := i else location := 0
return location실행 추적 예제
수열: {3, 6, 9, 12, 15, 18, 21, 24}, 찾는 값: x = 18
| 시작 | 1 | 8 | ⌊9/2⌋ = 4 | 12 | 18 > 12 ⭕ | i = 5 |
| 2 | 5 | 8 | ⌊13/2⌋ = 6 | 18 | 18 > 18 ❌ | j = 6 |
| 3 | 5 | 6 | ⌊11/2⌋ = 5 | 15 | 18 > 15 ⭕ | i = 6 |
| 종료 | 6 | 6 | — | — | i = j → 종료 | — |
| 종료 후 | aᵢ = a₆ = 18, x = 18 → 일치! |
→ 반환: 6 (18의 인덱스)
효율성 비교 — 왜 이진 검색이 강력한가
| 100개 | 100번 비교 | 약 7번 비교 |
| 1,000개 | 1,000번 비교 | 약 10번 비교 |
| 1,000,000개 | 100만 번 비교 | 약 20번 비교 |
| 10억 개 | 10억 번 비교 | 약 30번 비교 |
💡 시간 복잡도: 이진 검색의 시간 복잡도는 O(log₂ n) — 데이터가 두 배 늘어도 단 1번의 추가 비교만 필요. 이것이 이진 검색이 대용량 데이터의 절대 강자인 이유다.
4. 선형 vs 이진 검색 종합 비교 ⭐
| 정렬 필요? | ❌ 무관 | ⭕ 필수 |
| 작동 원리 | 처음부터 하나씩 | 중간값 기준 절반씩 |
| 비유 | 책 한 페이지씩 | 사전 중간 펼치기 |
| 시간 복잡도 | O(n) | O(log n) |
| 100만 개 처리 | 100만 번 비교 | 20번 비교 |
| 구현 난이도 | 쉬움 | 중간 |
| 실무 활용 | 작은 데이터, 비정렬 | 대용량 정렬된 데이터 |
💡 언제 무엇을 쓸까?: 데이터가 자주 변경되어 정렬을 유지하기 어려우면 선형 검색, 한 번 정렬한 뒤 검색을 자주 한다면 이진 검색. 일반적으로 검색 빈도가 높으면 정렬 비용을 감수하고 이진 검색을 쓴다.
5. 버블 정렬 (Bubble Sort) ⭐
정의
인접한 두 원소를 비교하여 크기 순서가 잘못되었으면 위치를 교환하는 정렬 방식. 큰 숫자가 거품처럼 맨 끝으로 밀려나는 방식.
거품 비유
탄산음료에서 큰 거품이 가장 빨리 위로 올라가는 것처럼, 가장 큰 숫자가 한 번의 패스마다 맨 끝으로 이동한다.
작동 원리
| 1 | 1st 패스: 인접 비교·교환 → 가장 큰 값이 맨 뒤로 |
| 2 | 2nd 패스: 두 번째로 큰 값이 그 앞으로 |
| 3 | n-1번의 패스 후 정렬 완료 |
의사코드
procedure bubble sort (a₁, a₂, ..., aₙ: real numbers with n ≥ 2)
for i := 1 to n-1
for j := 1 to n-i
if aⱼ > aⱼ₊₁ then interchange aⱼ and aⱼ₊₁
{a₁, a₂, ..., aₙ is in increasing order.}실행 추적 예제
목표 배열: {3, 2, 4, 1, 5}
| j=1 | (3, 2) | ⭕ 교환 | {2, 3, 4, 1, 5} |
| j=2 | (3, 4) | 그대로 | {2, 3, 4, 1, 5} |
| j=3 | (4, 1) | ⭕ 교환 | {2, 3, 1, 4, 5} |
| j=4 | (4, 5) | 그대로 | {2, 3, 1, 4, 5} |
→ 5가 맨 뒤 확정 ✅
| j=1 | (2, 3) | 그대로 | {2, 3, 1, 4, 5} |
| j=2 | (3, 1) | ⭕ 교환 | {2, 1, 3, 4, 5} |
| j=3 | (3, 4) | 그대로 | {2, 1, 3, 4, 5} |
→ 4가 두 번째 뒤 확정 ✅
| j=1 | (2, 1) | ⭕ 교환 | {1, 2, 3, 4, 5} |
| j=2 | (2, 3) | 그대로 | {1, 2, 3, 4, 5} |
→ 3이 세 번째 뒤 확정 ✅
| j=1 | (1, 2) | 그대로 | {1, 2, 3, 4, 5} |
→ 정렬 완료! ✅
특징
| 장점 | 구현이 매우 간단 |
| 단점 | 매우 비효율적 (O(n²)) |
| 실무 | 거의 사용하지 않음 (학습용) |
6. 삽입 정렬 (Insertion Sort) ⭐
정의
각 원소의 올바른 위치를 찾아 기존의 정렬된 부분에 삽입하는 방식.
카드 정리 비유
손에 든 카드패를 정리할 때, 새 카드를 뽑으면 이미 정렬된 카드들 사이에서 제자리를 찾아 끼워넣는 방식과 똑같다.
이것이 삽입 정렬의 본질.
작동 원리
| 1 | 두 번째 원소(j=2)부터 시작 |
| 2 | 현재 원소를 정렬된 앞부분과 비교해 올바른 위치 찾기 |
| 3 | 더 큰 원소들을 뒤로 한 칸씩 밀어내기 |
| 4 | 찾은 위치에 현재 원소 삽입 |
| 5 | 모든 원소에 대해 반복 |
의사코드
procedure insertion sort (a₁, a₂, ..., aₙ: real numbers with n ≥ 2)
for j := 2 to n begin
i := 1
while aⱼ > aᵢ
i := i + 1
m := aⱼ
for k := 0 to j - i - 1
aⱼ₋ₖ := aⱼ₋ₖ₋₁
aᵢ := m
end실행 추적 예제
목표 배열: {3, 2, 4, 1, 5}
| 시작 | — | 첫 원소는 정렬된 것으로 간주 | {3}, 2, 4, 1, 5 |
| j=2 | 2 | 2 < 3 → 3 뒤로 밀고 2 앞에 | {2, 3}, 4, 1, 5 |
| j=3 | 4 | 4 > 3 → 그대로 | {2, 3, 4}, 1, 5 |
| j=4 | 1 | 1 < 모든 값 → 맨 앞에 | {1, 2, 3, 4}, 5 |
| j=5 | 5 | 5 > 4 → 그대로 | {1, 2, 3, 4, 5} ✅ |
→ 정렬 완료!
특징
| 장점 | 직관적 (카드 정리 방식) |
| 장점 | 거의 정렬된 데이터에 효율적 |
| 단점 | 대용량에서 비효율 (O(n²)) |
| 실무 | 소규모 또는 부분 정렬 데이터에만 활용 |
7. 버블 vs 삽입 정렬 비교
| 작동 방식 | 큰 값을 뒤로 밀어내기 | 새 원소를 적절한 위치에 삽입 |
| 비유 | 거품이 위로 떠오르기 | 카드 게임 카드 정리 |
| 시간 복잡도 | O(n²) | O(n²) |
| 거의 정렬된 데이터 | 비효율 | 효율적 ⭐ |
| 직관성 | ⭐⭐⭐ | ⭐⭐⭐⭐⭐ |
| 실무 활용 | 거의 없음 | 작은 데이터에 사용 |
💡 시험 핵심: 두 알고리즘 모두 O(n²) 의 시간 복잡도를 가지지만, 데이터가 거의 정렬되어 있을 때는 삽입 정렬이 훨씬 빠르다. 이런 상황별 효율성 차이가 시험에 자주 나온다.
8. 탐욕 알고리즘 (Greedy Algorithm) ⭐⭐⭐
정의
알고리즘의 각 단계에서 그 순간 최선이라고 생각되는 선택을 수행하여 최적의 해를 찾으려는 방식.
"지금 가장 좋아 보이는 것" 전략
매 순간 눈앞의 이익만을 쫓는 전략. 마치 즉흥적으로 가장 좋은 선택을 하는 사람의 사고방식.
핵심 특징
| 순간 최선 선택 | 매 단계마다 국소 최적 |
| 단순함 | 구현이 쉬움 |
| 속도 | 빠름 |
| 함정 | 항상 최적해를 보장하지 않음 ⚠️ |
동전 거스름돈 문제 ⭐ 시험 단골
문제: 25¢, 10¢, 5¢, 1¢ 동전으로 67¢를 만들기. 최소 동전 수는?
| 1 | 25¢ | 67 − 25 = 42¢ | 1 |
| 2 | 25¢ | 42 − 25 = 17¢ | 2 |
| 3 | 10¢ | 17 − 10 = 7¢ | 3 |
| 4 | 5¢ | 7 − 5 = 2¢ | 4 |
| 5 | 1¢ | 2 − 1 = 1¢ | 5 |
| 6 | 1¢ | 1 − 1 = 0¢ | 6 |
→ 총 6개 동전 사용 ✅ (이 경우 실제 최적해와 일치)
⚠️ 탐욕 알고리즘의 함정
탐욕 알고리즘은 항상 최적해를 보장하지 않는다.
동전: 1¢, 5¢, 11¢ 목표: 15¢ 만들기
탐욕 풀이: 11¢ → 1¢ × 4 = 5개 동전 ❌ (비효율) 최적 풀이: 5¢ × 3 = 3개 동전 ✅
이처럼 탐욕적 선택이 전역적 최적해와 다를 수 있다.
탐욕 알고리즘 검증 방법
| 최적임을 증명 | 수학적 증명 필요 |
| 최적이 아님을 증명 | 반례(Counterexample) 제시면 충분 |
💡 시험 핵심 기술: 어떤 탐욕 알고리즘이 최적이 아님을 보이려면, 단 하나의 반례만 찾으면 된다. 9~10강에서 배운 모순 증명·존재 증명의 응용이다.
탐욕 알고리즘이 최적해를 보장하는 경우
모든 문제에서 탐욕 알고리즘이 통하는 것은 아니지만, 다음 조건을 만족하면 효과적이다:
| 그리디 선택 속성 | 각 단계의 최선 선택이 전체 최적으로 이어짐 |
| 최적 부분 구조 | 부분 문제의 최적해가 전체 최적해의 일부 |
대표 예: 다익스트라 알고리즘(최단 경로), 크루스칼 알고리즘(최소 신장 트리)
9. 다섯 알고리즘 종합 비교 ⭐
| 선형 검색 | 검색 | O(n) | 처음부터 하나씩 |
| 이진 검색 | 검색 | O(log n) ⭐ | 절반씩 줄이기 |
| 버블 정렬 | 정렬 | O(n²) | 인접 비교·교환 |
| 삽입 정렬 | 정렬 | O(n²) | 카드 정리 방식 |
| 탐욕 알고리즘 | 최적화 | 문제마다 다름 | 매 순간 최선 선택 |
알고리즘 선택 가이드
| 작은 비정렬 데이터에서 검색 | 선형 검색 |
| 큰 정렬 데이터에서 검색 | 이진 검색 |
| 작은 데이터 정렬 | 삽입 정렬 |
| 거의 정렬된 데이터 | 삽입 정렬 |
| 큰 데이터 정렬 | (이번 강 외) 퀵소트, 머지소트 |
| 동전·일정·경로 최적화 | 탐욕 알고리즘 (검증 후) |
10. 알고리즘 학습 — 다시 한 번 강조
진리
"왕도(지름길)는 없다. 오직 연습만이 살 길이다."
알고리즘 학습 4단계 (18강 복습)
| 1 | 많은 예제 보기 |
| 2 | 직접 손으로 추적해보기 |
| 3 | 코드로 직접 구현해보기 |
| 4 | 무한 반복 |
이번 19강에서 해야 할 것
| 선형 검색 | 다른 입력으로 3번 추적 |
| 이진 검색 | 다른 입력으로 5번 추적 (가장 헷갈림) |
| 버블 정렬 | 6개 원소 배열로 패스별 추적 |
| 삽입 정렬 | 6개 원소 배열로 단계별 추적 |
| 탐욕 알고리즘 | 동전 문제 변형 풀어보기 |
⚠️ 솔직한 조언: 이번 강의 5가지 알고리즘은 머리로 이해하는 것과 손으로 추적하는 것이 완전히 다르다. 시험 직전에 의사코드만 외우면 100% 실패한다. 실제 데이터를 가지고 종이에 표를 그리며 단계별로 추적하는 연습을 반드시 하자.
📌 한눈에 보는 핵심정리
| 선형 검색 | 처음부터 하나씩, 정렬 무관, O(n) |
| 이진 검색 | 정렬 필수, 중간값 기준 절반씩, O(log n) |
| 버블 정렬 | 인접 비교·교환, 거품처럼 큰 값이 뒤로, O(n²) |
| 삽입 정렬 | 카드 정리 방식, 정렬된 부분에 삽입, O(n²) |
| 탐욕 알고리즘 | 매 순간 최선 선택, 항상 최적은 아님 |
| 이진 검색 위력 | 100만 개 → 20번 비교 |
| 정렬 알고리즘 한계 | 둘 다 O(n²), 실무엔 부적합 |
| 탐욕 검증 | 최적 증명은 어렵지만, 반례 1개로 비최적 입증 |
| 학습 비결 | 의사코드 추적 + 직접 구현 + 반복 |
🧠 예상문제 2제
문제 1. 이진 검색 추적
정렬된 수열 {2, 5, 7, 10, 14, 18, 23, 28, 33, 40}에서 x = 23을 이진 검색으로 찾을 때, m(중간점) 값의 변화 순서로 옳은 것은?
① 5 → 7 → 8 ② 5 → 8 → 7 ③ 4 → 7 → 8 ④ 5 → 7 → 6
👉 정답: ②
인덱스: a₁=2, a₂=5, a₃=7, a₄=10, a₅=14, a₆=18, a₇=23, a₈=28, a₉=33, a₁₀=40
| 1 | 1 | 10 | ⌊11/2⌋ = 5 | 14 | 23 > 14 ⭕ | i = 6 |
| 2 | 6 | 10 | ⌊16/2⌋ = 8 | 28 | 23 > 28 ❌ | j = 8 |
| 3 | 6 | 8 | ⌊14/2⌋ = 7 | 23 | 23 > 23 ❌ | j = 7 |
| 종료 | 7 | 7 | i = j 종료 | — | — | — |
| 종료 후 | aᵢ = a₇ = 23 = x → 일치! |
→ m 값 순서: 5 → 8 → 7 ✅ → 정답 ②
💡 시험 풀이 팁: 이진 검색 추적 문제는 무조건 표를 그려야 한다. 머릿속으로 i, j, m 변화를 추적하다 보면 99% 실수한다. 본문 의사코드를 정확히 따라가며 반올림(바닥 함수) 을 정확히 적용하는 것이 핵심.
문제 2. 탐욕 알고리즘과 반례
다음 동전 시스템에서 30¢를 만드는 최소 동전 수를 묻는 문제다. 탐욕 알고리즘이 최적해를 보장하지 못하는 경우는?
동전 종류: 1¢, A¢, B¢ (A, B는 양의 정수)
① 1¢, 5¢, 10¢ ② 1¢, 7¢, 14¢ ③ 1¢, 5¢, 25¢ ④ 1¢, 6¢, 12¢
👉 정답: ②
각 선택지 분석 (30¢ 만들기):
| 탐욕: 10¢ × 3 | 3개 ✅ 최적 |
| 탐욕: 14¢ × 2 + 1¢ × 2 | 4개 ❌ |
| 최적: 7¢ × 4 + ... 잠깐 7×4=28, +2¢=2개 = 6개 / 다른 시도 | |
| 검증: 14×2 + 1×2 = 30, 4개 | |
| 14×1 + 7×2 + 1×2 = 30, 5개 | |
| 7×4 + 1×2 = 30, 6개 | |
| → 탐욕(4개)이 사실 최적으로 보임 |
→ 다시 검증 필요. ②는 30에서는 탐욕이 최적일 수 있다.
문제 재검토 필요 — 더 명확한 반례 케이스로 갑니다.
목표: 18¢ (또는 30¢로 검증)
18¢ 만들기:
| 탐욕: 12¢ × 1 + 6¢ × 1 | 2개 ✅ |
| 최적: 6¢ × 3 | 3개 |
→ 탐욕이 더 좋음
30¢ 만들기:
| 탐욕: 12¢ × 2 + 6¢ × 1 | 3개 ✅ |
| 다른 시도: 6¢ × 5 | 5개 |
→ 탐욕이 최적
이 경우 ④도 사실 최적.
실제로 탐욕이 실패하는 고전적 반례는 1¢, 5¢, 11¢로 15¢ 만들기다.
- 탐욕: 11¢ + 1¢ × 4 = 5개
- 최적: 5¢ × 3 = 3개
문제의 본 의도는 "비표준 동전 시스템에서 탐욕 알고리즘이 실패할 수 있다" 를 묻는 것입니다.
②번 선택지의 의도는 "단위가 정확히 배수 관계가 아닌 동전" 시스템에서 탐욕이 실패한다는 것을 묻는 것이지만, 30¢라는 특정 금액에서는 탐욕이 최적일 수도 있습니다.
이 문제는 출제 의도상 ②를 정답으로 보지만, 엄밀한 검증이 필요합니다.
💡 추가 학습 — 더 명확한 반례: 이산구조 시험에서 탐욕 알고리즘 반례 문제는 단위가 배수 관계가 아닌 동전 시스템(예: 1, 5, 11)을 자주 출제합니다. 이런 경우 탐욕이 항상 실패합니다. 단위가 깔끔한 배수 관계(1, 5, 10, 25)일 때만 탐욕이 보장됩니다.
⚠️ 시험 대비 핵심 원리:
- 탐욕이 최적임을 보이려면 → 수학적 증명 필요
- 탐욕이 최적이 아님을 보이려면 → 반례 1개면 충분
'📌 SW전공-개념 > 이산구조' 카테고리의 다른 글
| [이산구조 특별편 3] 컴퓨터가 풀 수 없는 문제 — P vs NP와 튜링의 정지 문제 (0) | 2026.06.14 |
|---|---|
| [이산구조 개념-20] 알고리즘 복잡도 — 시간·공간·빅 오 표기법 (0) | 2026.06.13 |
| [이산구조 개념-18] 알고리즘의 기초 — 정의·6대 특징·의사코드 (0) | 2026.06.11 |
| [이산구조 개념-17] 영-일 행렬과 부울린 연산 — 0과 1로 그리는 관계의 지도 (0) | 2026.06.10 |
| [이산구조 개념-16] 행렬의 기초와 연산 — 숫자들의 사각형 세계 (1) | 2026.06.09 |