[전산직(데이터) 공무원 대비] 알고리즘 기초부터 파헤치기 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. 검색 (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):
        • • 충돌 나면? 다른 해시 함수를 한 번 더 돌려서 점프할 보폭을 정한다.
          • 규칙적이지 않게 띄엄띄엄 저장해서 군집화 방지.
  2. 체이닝 (Chaining):
     • 충돌 나면? 해당 칸에 연결 리스트(Linked List)를 달아서 줄줄이 매달아 버린다. 
     • 테이블이 꽉 차도 계속 데이터를 넣을 수 있지만, 추가 메모리가 든다.

2-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번 인덱스] 저장

 

 

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

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

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

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

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

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

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

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

 

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

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

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