[전산직(데이터) 공무원 대비] 알고리즘 기초부터 파헤치기 3

이제 알고리즘의 허리 역할을 하는 정렬과 탐색으로 넘어가 보자.

공무원 시험에서는 이 정렬 알고리즘이 얼마나 빠른지(시간 복잡도), 메모리는 얼마나 쓰는지(공간 복잡도), 그리고 데이터가 어떻게 변하는지를 묻는다.

1. 정렬의 양대 산맥: 퀵(Quick) vs 병합(Merge)

이 둘은 모두 분할 정복(Divide & Conquer)을 사용하고 평균 $O(n \log n)$으로 매우 빠르지만, 성격이 완전 다르다.

(1) 퀵 정렬 (Quick Sort) - "불안정하지만 빠른 천재"

• 원리: 피벗(Pivot)이라는 기준점을 하나 잡는다. 피벗보다 작은놈은 왼쪽, 큰 놈은 오른쪽으로 몰아넣고(Partition) 양쪽을 각각 다시 재귀 호출한다.
• 장점: 추가 메모리가 거의 필요 없고(In-place), 캐시 효율(Cache Hit)이 좋아 실제로는 가장 빠르다.
• 단점 (치명적):
  • 불안정 정렬(Unstable): 같은 값의 순서가 뒤집힐 수 있다.
  • 최악의 경우 $O(n^2)$: 피벗을 잘못 잡아서(예: 이미 정렬된 배열에서 맨 앞을 피벗으로 함) 한쪽으로만 쏠릴 때 급격히 느려진다.

(2) 병합 정렬 (Merge Sort) - "안정적인 모범생"

• 원리: 일단 무조건 반으로 쪼갭니다. 더 이상 못 쪼갤 때까지(크기가 1) 쪼갠 다음, 합치면서(Merge) 정렬한다.
• 장점:
  • 입력 데이터가 어떻든 항상 $O(n \log n)$을 보장한다.
  • 안정 정렬(Stable): 순서가 유지된다.
• 단점: 정렬된 데이터를 잠시 저장할 별도의 메모리 공간($O(n)$)이 반드시 필요하다. (공간 복잡도가 높음)

 

[핵심 비교표] 머릿속에 저장!

비교 항목	퀵 정렬 (Quick Sort)	병합 정렬 (Merge Sort)
핵심 원리	피벗 기준 분할 (Partition)	일단 반으로 쪼개고 병합
평균 시간 복잡도	$O(n \log n)$	$O(n \log n)$
최악 시간	$O(n^2)$ (피벗 최소/최대로 잡을 시)	$O(n \log n)$ (항상 보장)
메모리 (공간 복잡도)	적게 씀 ($O(\log n)$ 스택 메모리만 사용)	많이 씀 ($O(n)$ 배열 필요)
안전성	불안정 (순서 뒤집힘)	안정 (순서 유지)
적합한 상황	일반적인 배열 정렬 (메모리 제한)	Linked List 정렬 (순차 접근 유리)

• 암기 포인트:
  • "메모리가 부족한 시스템이다?" $\rightarrow$ 퀵 정렬 (단, 최악 방지 피벗 선정 필요)
  • "입력 데이터의 정렬 상태와 상관없이 일정한 속도가 필요하다?" $\rightarrow$ 병합 정렬
  • "Linked List를 정렬한다?" $\rightarrow$ 병합 정렬 (임의 접근이 안 돼도 순차적으로 합치기 좋음)

 

 

1-1. 최신 기출 맛보기

문제 1. 정렬 비교

퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)에 대한 설명으로 옳지 않은 것은?

1. 퀵 정렬은 피벗(Pivot)의 선택에 따라 성능 차이가 크게 발생할 수 있다.
2. 병합 정렬은 연결 리스트(Linked List)를 정렬할 때 배열보다 효율적으로 구현할 수 있다.
3. 퀵 정렬은 추가적인 메모리 공간을 많이 사용하므로, 메모리가 제한된 시스템에서는 병합 정렬이 더 선호된다.
4. 병합 정렬은 입력 데이터의 정렬 상태와 무관하게 항상 일정한 시간 복잡도를 가진다.

(힌트) 메모리를 "누가 더 많이 먹는지(배열 공간 vs 스택 공간)"를 잘 따져보세요!

정답: 3번

완전히 반대로 설명했다. 병합 정렬은 합병 과정에서 입력 크기만큼의 추가 배열($O(n)$)이 필요하여 메모리를 많이 먹는다. 반면 퀵 정렬은 재귀 호출을 위한 스택 메모리($O(\log n)$)만 조금 쓰므로 메모리가 제한된 곳에서 유리하다.

 

2. 기타 정렬 알고리즘 (코드 식별 & 특수 상황용)

시험에서 코드를 보여주거나 특수한 상황을 주고 어떤 정렬인지 묻는 유형 대비용

(2) 삽입 정렬 (InsertionSort) - "이미 정렬된 데이터의 제왕"

• 원리: 데이터를 하나씩 뽑아서, 앞쪽의 이미 정렬된 부분 사이의 적절한 위치에 끼워 넣는다.
• 코드 특징: key 값을 잡고, while 문으로 나보다 큰 놈들을 뒤로 미는(Shift) 연산이 보임.

(2) 쉘 정렬 (Shell Sort) - "삽입 정렬의 업그레이드"

• 등장 배경: 삽입 정렬이 '역순'으로 되어 있으면 이동 횟수가 너무 많은 단점을 해결.
• 핵심: 일정한 간격(Gap) (예: 5, 3, 1)을 두고 띄엄띄엄 부분 리스트를 만들어 삽입 정렬을 수행함.

(3) 선택 정렬 (Selection Sort) - "최솟값 집착남"

• 원리: 리스트 전체를 훑어서 **가장 작은 값(Min)**을 찾아 맨 앞과 자리를 바꿈.
• 특징: 교환(Swap) 횟수가 가장 적음. 하지만 비교 횟수는 많아서 항상 $O(N^2)$임.

 

2-1. 최신 기출 맛보기

문제 1. 주어진 데이터에 알맞는 알고리즘

데이터가 100만 개 있는데, 그중 단 5개만 제자리에 있지 않고 나머지는 모두 이미 정렬되어 있다. 이 데이터를 오름차순으로 정렬할 때 가장 빠른 알고리즘은?

1. 퀵 정렬 (Quick Sort)
2. 병합 정렬 (Merge Sort)
3. 선택 정렬 (Selection Sort)
4. 삽입 정렬 (Insertion Sort)

정답: 4번 

• 퀵, 병합 정렬은 데이터 상태와 무관하게 쪼개고 합치느라 평균 $O(N \log N)$의 시간이 걸린다.
• 하지만 삽입 정렬은 이미 정렬된 부분은 비교만 쓱 하고 지나가기 때문에, 이런 '거의 정렬된' 상황에서는 **$O(N)$**에 가까운 압도적인 속도를 낸다.

 

문제 2. 쉘 정렬

다음 배열을 쉘 정렬(Shell Sort)을 사용하여 정렬하고자 한다. 간격(Gap)을 3으로 설정하여 첫 번째 패스를 수행한 후의 중간 결과로 옳은 것은?

초기 상태:
 [9, 1, 2, 5, 3, 4]

1. [1, 2, 3, 4, 5, 9] 
2. [5, 3, 4, 9, 1, 2] 
3. [5, 1, 2, 9, 3, 4] 
4. [2, 1, 5, 3, 4, 9]

정답: 3번

• 간격이 3이므로 인덱스가 3만큼 떨어진 녀석끼리 짝을 지어 비교/교환
  • 그룹 1 (인덱스 0, 3): 9와 5 비교 $\rightarrow$ 5가 작으므로 교환 $\rightarrow$ [5, ..., 9, ...]
  • 그룹 2 (인덱스 1, 4): 1과 3 비교 $\rightarrow$ 1이 작으므로 그대로.
  • 그룹 3 (인덱스 2, 5): 2와 4 비교 $\rightarrow$ 2가 작으므로 그대로.

 

문제3. 코드 식별 문제

다음 C언어 코드가 수행하는 정렬 알고리즘의 이름은?

for (i = 0; i < n-1; i++) {
    min_idx = i;                // 1. 일단 맨 앞을 제일 작다고 가정
    for (j = i+1; j < n; j++) {
        if (list[j] < list[min_idx]) {
            min_idx = j;        // 2. 더 작은 놈 발견하면 인덱스 갱신
        }
    }
    swap(list[i], list[min_idx]); // 3. 제일 작은 놈을 맨 앞으로 데려옴
}

1. 삽입 정렬
2. 선택 정렬
3. 버블 정렬
4. 퀵 정렬

정답: 2번

• 코드의 핵심은 min_idx (최솟값의 위치)를 찾는 것.
• "가장 작은 값을 선택(Select)해서 맨 앞으로 보낸다" $\rightarrow$ 선택 정렬
• 참고: 삽입 정렬은 key 값을 들고 뒤로 미는(j--) 코드가 나온다.

 

3. 검색 (Searching) & 해싱 (Hashing)

데이터를 찾는 방법은 크게 '비교' 방식과 '주소 계산' 방식으로 나뉜다.

1. 이진 탐색 (Binary Search): "업-다운 게임"

• 조건: 반드시 데이터가 정렬되어 있어야 한다.
• 원리: 중간값(Middle)을 찍어서 찾으려는 값보다 크면 왼쪽, 작으면 오른쪽만 본다. (한 번 비교할 때마다 후보가 절반으로 줄어듦)
• 시간 복잡도: $O(\log n)$ (순차 탐색보다 빠름)
• 최대 비교 횟수: $\lfloor \log_2 n \rfloor + 1$ (공식 중요!)

2. 해싱 (Hashing): "주소로 바로 찾아가기"

• 개념: Key를 해시 함수에 넣으면 주소(Index)가 즉시 나온다.
• 시간 복잡도: 이상적인 경우 $O(1)$ (단 한 방에 찾음!)
• 문제점: 서로 다른 키가 같은 주소를 가리키는 충돌(Collision) 발생.
• [심화 🚨] 충돌(Collision) 해결 기법:
  1. 개방 주소법 (Open Addressing): 빈방을 찾아서 떠도는 방식이다. 별도의 메모리가 필요 없다.
     1. 선형 조사법 (Linear Probing):
        • 충돌 나면? 바로 옆 칸($+1$) 을 본다. 또 차 있으면? 그 옆 칸($+2$)...
        • 문제점: 한 곳에 데이터가 뭉치는 군집화(Clustering) 현상이 생겨 성능 저하 발생. ($O(1) \to O(n)$)
     2. 이중 해싱 (Double Hashing):
        • • 충돌 나면? 다른 해시 함수를 한 번 더 돌려서 점프할 보폭을 정한다.
          • 규칙적이지 않게 띄엄띄엄 저장해서 군집화 방지.
          • $h(k, i) = (h_1(k) + i \times h_2(k)) \pmod M$
          • 첫 번째 해시($h_1$)로 주소를 잡고, 충돌 시 두 번째 해시($h_2$) 결과만큼 보폭(Jump)을 주어 이동함.
  2. 체이닝 (Chaining):
     • 충돌 나면? 해당 칸에 연결 리스트(Linked List)를 달아서 줄줄이 매달아 버린다. 
     • 테이블이 꽉 차도 계속 데이터를 넣을 수 있지만, 추가 메모리가 든다.

3-1. 최신 기출 맛보기

문제 1. 해싱 주소 계산

크기가 11인 해시 테이블(인덱스 0~10)이 있다.

해시 함수 $h(k) = k \pmod 11$ 을 사용하고, 충돌 시 선형 조사법(Linear Probing)으로 해결한다.

데이터 [12, 25, 45, 14]가 순서대로 들어올 때, 14가 저장될 인덱스는?

1. 1
2. 4
3. 5
4. 3

(힌트) 순서로 빈 방을 찾아보자

 

정답: 2번 

• 12: $12 \% 11 = 1$ → [1번 인덱스] 저장
• 25: $25 \% 11 = 3$ → [3번 인덱스] 저장
• 45: $45 \% 11 = 1$ → (1번 꽉 참, 충돌!) → 옆 칸(2번) 확인 → [2번 인덱스] 저장
• 14: $14 \% 11 = 3$ → (3번 꽉 참, 충돌!) → 옆 칸(4번) 확인 → [4번 인덱스] 저장

 

4. [심화] 문자열 매칭 (String Matching)

긴 글($T$)에서 특정 단어($P$)를 찾는 특수 알고리즘이다. 이름과 특징만 매칭해도 문제를 풀 수 있다.

(1) 브루트 포스 (Brute Force)

• 무식하게 한 칸씩 비교. 틀리면 한 칸 이동해서 처음부터 다시.
• 시간 복잡도: $O(MN)$ (매우 느림)

(2) KMP 알고리즘 (Knuth-Morris-Pratt)

• 글자가 틀렸을 때, "어디까지 맞았는지 아니까, 접두사/접미사 일치 길이만큼 점프하자!"
• 핵심 키워드: 실패 함수 ($\pi$(pi) 배열: 일치하는 길이 미리 계산), Backtracking 없음.
• 시간 복잡도 : $O(N+M)$ (검색할 문자열 길이 + 패턴 길이). 뒤로 돌아가지 않음(Backtracking X).

(3) 라빈-카프 (Rabin-Karp)

• 문자열을 숫자(해시값)로 변환해서 비교.
• 핵심 키워드: 롤링 해시 (Rolling Hash) - 창문을 밀듯이 이전 값에 맨 앞 값 빼고 맨 뒤 값 더해서 해시 갱신.
• 시간 복잡도 : 평균 $O(N+M)$, 최악 $O(MN)$ (해시 충돌 시).

(4) 보이어-무어 알고리즘 (Boyer-Moore)

• 패턴의 오른쪽 끝에서 왼쪽으로 비교한다. (KMP와 반대 방향!)
• 원리: 글자가 틀렸을 때, 패턴에 아예 없는 글자라면 패턴 길이만큼 통째로 건너뜀(Skip).
• 시간 복잡도 : 일반적인 상용 프로그램(문서 편집기 찾기 기능)에서 가장 많이 쓰임. 최선의 경우 $O(N/M)$으로 패턴이 길수록 오히려 빨라짐.

(5) 트라이 (Trie) - "문자열 검색 전용 트리"

• 문자열 집합을 저장하고 빠르게 검색하기 위한 트리(Tree) 자료구조.
• 구조: 루트에서부터 글자 하나씩 링크를 따라 내려가는 구조. (예: 자동 완성 기능)
• 시간 복잡도: 찾으려는 문자열의 길이가 $L$일 때, $O(L)$.
  • 중요: 데이터가 100만 개가 있어도, 단어 길이($L$)만큼만 가면 찾음. 데이터 개수($N$)와 무관하게 빠름.

 

👉 더 많은 정렬과 탐색 관련 문제를 풀어보고 싶다면?

제미나이가 만든 퀴즈 풀어보기 https://gemini.google.com/share/3a1d980cc779

[제미나이 퀴즈 오답노트]

[6번 문제]

실패 함수(Failure Function)의 정의:

• 패턴 내에서 "접두사(Prefix)와 접미사(Suffix)가 일치하는 최대 길이"를 저장한다.
• 왜? 매칭에 실패했을 때, "앞부분 이만큼은 똑같으니까 다시 비교하지 말고 건너뛰자!"라고 점프할 위치를 알려주기 때문에.
• 실전 계산: ABABAC의 $\pi$ 배열 구하기
  1. A (길이 1): 접두/접미사 없음 $\to$ 0
  2. AB (길이 2): A $\neq$ B $\to$ 0
  3. ABA (길이 3): 앞의 A == 뒤의 A $\to$ 1
  4. ABAB (길이 4): 앞의 AB == 뒤의 AB $\to$ 2
  5. ABABA (길이 5): 앞의 ABA == 뒤의 ABA $\to$ 3
  6. ABABAC (길이 6): 앞의 ABABA... 뒤가 C라 안 맞음 $\to$ 0
• 글자를 하나씩 늘려가며 (접두사 == 접미사)가 되는 가장 긴 길이를 찾는다.

[7번 문제] 공간 복잡도가 가장 큰 정렬 알고리즘은?

• 퀵 정렬: 재귀 호출을 위한 스택 메모리만 필요 $\rightarrow$ $O(\log n)$
• 힙 정렬: 배열 안에서 자리만 바꿈 (In-place) $\rightarrow$ $O(1)$
• 선택 정렬: 변수 하나(temp)만 있으면 됨 $\rightarrow$ $O(1)$
• 병합 정렬 (Merge Sort): (정답)
  • 두 리스트를 합칠 때, 데이터를 잠시 옮겨 담을 입력 크기만한 임시 배열(List)이 반드시 필요하다.
  • 공간 복잡도: $O(n)$ (가장 많이 씀)

한번 더 퀵 정렬과 병합 정렬 비교하고 넘어가기!

퀵 정렬 vs 병합 정렬 (결정적 차이)

관련 문제: 1번, 4번, 7번

"둘 다 $O(n \log n)$인데 뭐가 달라요?"라고 묻는다면 아래 3가지를 대답해야 한다.

1. 안정성 (Stability):
   • 병합(Merge): 안정. 합칠 때(Merge) 앞의 리스트에 있는 값을 먼저 넣으면 순서가 유지.
   • 퀵(Quick): 불안정. 피벗을 기준으로 휙휙 교환(Swap)하다 보면 원래 순서가 뒤집힘.
2. 메모리 (Space Complexity):
   • 병합(Merge): 합칠 때 데이터를 잠시 둘 입력 크기만한 임시 배열($O(n)$)이 무조건 필요. (공간 낭비 큼)
   • 퀵(Quick): 추가 배열 없이 재귀 호출을 위한 스택 공간($O(\log n)$)만 있으면 됨. (제자리 정렬)
3. 최악의 경우 (Worst Case):
   • 퀵(Quick): 이미 정렬된 데이터에서 피벗을 최소/최대로 잡으면 $O(n^2)$이 됨. (분할이 1개, N-1개로 됨)
   • 병합(Merge): 데이터가 정렬돼 있든 말든 무조건 반으로 쪼개므로 항상 $O(n \log n)$.

 

[8번 문제] 시간 복잡도가 $O(N+M)$인 알고리즘은?

• 브루트 포스: 본문($N$)의 모든 위치에서 패턴($M$)을 비교 $\rightarrow$ $O(NM)$ (느림)
• 이진 탐색: 정렬된 숫자를 찾는 것 $\rightarrow$ $O(\log n)$ (문자열 매칭 아님)
• 버블 정렬: 인접한 두 원소를 비교해서 자리를 바꿈 $\rightarrow$ $O(n^2)$
• KMP 알고리즘: (정답)
  • 본문은 뒤로 돌아가지 않고 쭉 훑음 ($N$)
  • 패턴은 미리 실패 함수를 계산해둠 ($M$)
  • 둘을 합쳐 $O(N+M)$이라는 환상적인 속도를 냄.

[9번 문제] 비교 정렬의 한계 (Lower Bound)

• "왜 정렬은 $O(n \log n)$보다 빨라질 수 없나요?"
• 두 수를 비교(Yes/No)해서 순서를 정하는 방식(비교 기반 정렬)은 수학적으로 의사 결정 트리(Decision Tree)의 높이만큼 시간이 걸림.
• 이 트리의 최소 높이가 $\log(n!)$이며, 이는 약 $n \log n$에 해당.
• (참고: 비교하지 않는 '기수 정렬(Radix Sort)' 등은 $O(n)$이 가능하지만, 특수한 경우에만 사용.)

[10번 문제] 이진 탐색(Binary Search)에 가장 적합한 자료구조는?

"업-다운 게임"을 생각하면 사회자가 "가운데 숫자를 봐!"라고 했을 때, 즉시($O(1)$) 볼 수 있어야 함.

• 정렬된 배열 (Sorted Array): arr[mid]로 한 방에 접근 가능. $\rightarrow$ 최적 ($O(\log n)$ 유지)
• 정렬된 연결 리스트 (Sorted Linked List):
  • 가운데를 보려면? "첫 번째 노드야, 다음, 다음, 다음..." 하고 절반을 걸어가야 함.
  • 중간 가는 데만 $O(n)$이 걸리므로, 이진 탐색의 의미가 사라짐. (결국 $O(n)$ 됨)

결론: 이진 탐색은 반드시 '인덱스로 접근 가능한(Random Access)' 배열에서만 쓴다. 

다음 포스팅에서는 트리와 힙에 대해 정리해 보겠다.