알고리즘 — 정렬과 탐색

🎯 이 강에서 배우는 것

이 섹션에서는 7강의 학습 목표와 핵심 개념의 전체 구조를 살펴보겠습니다.

정보처리기사 필기 시험에서 알고리즘 문제는 3과목(데이터베이스 구축)과 2과목(소프트웨어 개발) 모두에서 출제됩니다. 특히 정렬 알고리즘의 시간복잡도와 특정 조건에서 유리한 알고리즘 선택 문제는 거의 매회 출제되는 고빈도 유형입니다.

이 강에서는 6대 정렬 알고리즘(버블·선택·삽입·퀵·합병·힙)을 단계별로 추적하고, 이진 탐색의 전제 조건과 동작 방식, 해시의 충돌 해결 방법, 그리고 알고리즘 설계 전략(분할정복·동적계획법·탐욕)을 체계적으로 정리합니다.

기출 함정 패턴으로 가장 많이 틀리는 것은 퀵 정렬의 최악 시간복잡도를 O(n log n)으로 착각하거나 합병 정렬의 공간복잡도를 O(1)로 혼동하는 경우입니다. 이 강을 마치면 이런 함정을 완벽히 피할 수 있게 됩니다.

🔄 버블·선택·삽입 정렬 — 단순 정렬의 이해

이 섹션에서는 시간복잡도 O(n²)에 속하는 세 가지 단순 정렬 알고리즘을 살펴보겠습니다.

버블 정렬(Bubble Sort)은 인접한 두 원소를 비교하여 순서가 틀리면 교환하는 방식입니다. 배열 [5, 3, 8, 1, 2]를 오름차순으로 정렬할 때, 1회전에서는 5와 3을 비교해 교환, 5와 8은 유지, 8과 1을 교환, 8과 2를 교환하여 [3, 5, 1, 2, 8]이 됩니다. 가장 큰 원소가 맨 뒤로 이동하는 것을 확인할 수 있습니다.

선택 정렬(Selection Sort)은 전체 배열에서 최솟값을 찾아 맨 앞 원소와 교환하는 방식입니다. 1회전에서 최솟값 1을 찾아 5와 교환 → [1, 3, 8, 5, 2], 2회전에서 나머지 중 최솟값 2를 찾아 3과 교환 → [1, 2, 8, 5, 3] 순으로 진행됩니다. 교환 횟수가 버블 정렬보다 적은 것이 특징입니다.

삽입 정렬(Insertion Sort)은 정렬된 부분에 새 원소를 적절한 위치에 삽입하는 방식입니다. 배열이 거의 정렬된 상태일 때 O(n)에 가까운 성능을 보이는 것이 가장 큰 특징입니다. 이미 정렬된 배열에 대해서는 세 가지 중 가장 빠릅니다.

⚡ 퀵·합병·힙 정렬 — 고급 정렬과 복잡도

이 섹션에서는 평균 O(n log n) 성능을 보이는 고급 정렬 알고리즘 세 가지를 살펴보겠습니다.

퀵 정렬(Quick Sort)은 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 재귀 정렬하는 방식입니다. 평균 O(n log n)이지만 이미 정렬된 배열에서 피벗을 항상 최솟값/최댓값으로 선택하면 최악 O(n²)이 됩니다. 실제로는 가장 빠른 알고리즘으로 알려져 있으며 제자리 정렬(in-place)로 공간복잡도 O(log n)입니다.

합병 정렬(Merge Sort)은 배열을 반으로 나누고 각각 정렬한 뒤 합치는 방식입니다. 분할 단계와 합병 단계가 명확히 구분됩니다. 최선·평균·최악 모두 O(n log n)으로 안정적이나, 합병을 위한 추가 배열이 필요하여 공간복잡도 O(n)이 됩니다. 이 점이 힙 정렬과의 차이입니다.

힙 정렬(Heap Sort)은 최대 힙(또는 최소 힙) 구조를 활용합니다. 먼저 배열을 최대 힙으로 구성(heapify)한 뒤, 루트(최댓값)를 맨 뒤로 이동시키고 힙 크기를 줄여가며 반복합니다. 최선·평균·최악 모두 O(n log n)이며 추가 공간 없이 제자리 정렬이 가능하여 공간복잡도 O(1)입니다.

📊 정렬 알고리즘 시간·공간복잡도 비교표

이 섹션에서는 6대 정렬 알고리즘의 복잡도를 한눈에 비교하는 핵심 표를 살펴보겠습니다.

아래 표는 기출에서 가장 많이 참조되는 정렬 알고리즘 비교표입니다. 반드시 암기해야 합니다.

알고리즘	최선	평균	최악	공간	안정성
버블 정렬	O(n)	O(n²)	O(n²)	O(1)	안정
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)	불안정
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)	안정
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(log n)	불안정
합병 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)	안정
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)	불안정

암기법: "버선삽은 n²이고 퀵합힙은 n log n" — 단, 퀵은 최악이 n²임을 주의하세요. 안정 정렬은 버블·삽입·합병이고(BSM = Bubble Stable Merge), 나머지는 불안정입니다.

기출 함정: "합병 정렬의 공간복잡도는 O(1)이다" → 틀림(O(n)). "힙 정렬은 안정 정렬이다" → 틀림(불안정). "퀵 정렬의 최악 시간복잡도는 O(n log n)이다" → 틀림(O(n²)).

🔍 이진 탐색과 해시 탐색

이 섹션에서는 순차 탐색보다 효율적인 이진 탐색과 O(1) 탐색을 지원하는 해시 탐색을 살펴보겠습니다.

이진 탐색(Binary Search)의 전제 조건은 배열이 반드시 정렬되어 있어야 한다는 것입니다. 정렬되지 않은 배열에는 이진 탐색을 적용할 수 없습니다. 동작 방식은 중간값(mid)과 목표값을 비교하여 왼쪽 절반 또는 오른쪽 절반으로 탐색 범위를 줄여가는 것입니다.

예를 들어 [1, 3, 5, 7, 9, 11, 13]에서 11을 찾는 경우: mid=7(인덱스 3), 11>7이므로 오른쪽 절반 → mid=11(인덱스 5), 발견. 시간복잡도는 O(log n)입니다.

해시 탐색(Hash Search)은 해시 함수를 통해 키를 인덱스로 변환하여 O(1) 평균 탐색을 실현합니다. 하지만 해시 충돌(Collision)이 발생할 수 있습니다.

충돌 해결 방법	원리	특징
체이닝(Chaining)	같은 인덱스에 연결 리스트로 저장	삭제 용이, 추가 메모리 필요
개방 주소법(Open Addressing)	충돌 시 다른 빈 슬롯 탐색	추가 메모리 불필요, 삭제 복잡
선형 조사(Linear Probing)	충돌 시 순차적으로 다음 슬롯 탐색	1차 군집 현상 발생 가능
이중 해싱(Double Hashing)	두 번째 해시 함수로 탐색 간격 결정	군집 현상 최소화

기출 함정: "해시 탐색의 최악 시간복잡도는 O(1)이다" → 틀림. 최악은 O(n)이며 O(1)은 평균입니다. 체이닝과 개방 주소법의 특성 차이를 묻는 문제가 자주 출제됩니다.

🧩 알고리즘 설계 전략 — 분할정복·동적계획법·탐욕

이 섹션에서는 세 가지 핵심 알고리즘 설계 전략을 비교하고 각각의 적용 사례를 살펴보겠습니다.

분할정복(Divide and Conquer)은 문제를 더 작은 부분 문제로 분할하고, 각각을 독립적으로 해결한 뒤 결과를 합치는 방식입니다. 핵심은 부분 문제들이 독립적이라는 점입니다. 대표 알고리즘으로 퀵 정렬, 합병 정렬, 이진 탐색, 카라츠바 알고리즘이 있습니다.

동적 계획법(Dynamic Programming, DP)은 분할정복과 비슷하지만 부분 문제들이 중복된다는 차이가 있습니다. 이미 계산한 결과를 저장해두고 재사용하여 중복 계산을 방지합니다. 구현 방식으로는 두 가지가 있습니다.

• 메모이제이션(Memoization): 하향식(Top-down) — 재귀 호출 결과를 캐싱
• 타뷸레이션(Tabulation): 상향식(Bottom-up) — 작은 문제부터 테이블에 저장

대표 문제: 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제, 플로이드-워샬 최단 경로.

탐욕 알고리즘(Greedy Algorithm)은 각 단계에서 지역 최적해(locally optimal)를 선택하여 전체 최적해를 구하는 방식입니다. 항상 최적해를 보장하지 않지만 특정 문제에서는 최적해를 구할 수 있습니다. 대표 알고리즘: 크루스칼(최소 신장 트리), 프림, 다익스트라(최단 경로), 허프만 코딩, 거스름돈 문제.

설계 전략	부분 문제	결과 재사용	최적해 보장	대표 예
분할정복	독립적	X	O	합병 정렬, 퀵 정렬
동적 계획법	중복	O	O	피보나치, LCS, 배낭
탐욕 알고리즘	독립적	X	조건부	다익스트라, 허프만

암기법: "분할독립, 동적중복, 탐욕지역" — 분할정복은 독립 분할, 동적 계획법은 중복 부분 문제, 탐욕은 지역 최적 선택으로 외웁니다.

기출 함정: "동적 계획법은 항상 탐욕 알고리즘보다 효율적이다" → 틀림. "분할정복은 중복된 부분 문제를 메모이제이션으로 해결한다" → 틀림(동적 계획법의 특성).

📌 7강 핵심 요약과 8강 예고

이 섹션에서는 7강 전체 내용을 압축 정리하고 기출 암기 포인트를 최종 확인합니다.

정렬 복잡도 최종 암기 포인트: 버블·선택·삽입은 O(n²), 퀵·합병·힙은 O(n log n). 퀵은 최악 O(n²), 합병은 공간 O(n), 힙은 공간 O(1). 안정 정렬은 버블·삽입·합병(BSM).

탐색 핵심: 이진 탐색은 정렬 필수 + O(log n), 해시는 평균 O(1)이나 최악 O(n). 충돌 해결은 체이닝(연결 리스트)과 개방 주소법(빈 슬롯 탐색) 두 가지.

알고리즘 설계 전략: 분할정복(독립 분할)·동적 계획법(중복 캐싱)·탐욕(지역 최적 선택) 세 가지의 차이를 정확히 구분할 수 있어야 합니다.

다음 8강에서는 소프트웨어 테스트 — 블랙박스·화이트박스 기법의 차이와 V-모델, 테스트 커버리지 개념을 완벽히 정리합니다.