정렬·검색과 시간 복잡도
쉽게 말하면
정렬은 데이터를 크기 순서로 줄 세우는 일이에요. 방법마다 속도가 달라요. 삽입·선택·버블 정렬은 이해하기 쉽지만 데이터가 많으면 느려요(n²). 퀵·힙·합병 정렬은 빨라요(n log n). 검색은 원하는 값을 찾는 일인데, 정렬된 데이터라면 가운데부터 보고 절반씩 버리는 이진 검색이 빨라요. 해싱은 계산으로 위치를 바로 찾아가는 방법이에요.
시험용 정의
정렬은 데이터를 정해진 순서로 재배치하는 것이다. 삽입 정렬은 두 번째 자료부터 앞의 정렬된 부분의 알맞은 자리에 끼워 넣는다. 선택 정렬은 남은 자료 중 최솟값을 골라 앞으로 보낸다. 버블 정렬은 이웃한 두 자료를 비교해 교환하며 큰 값을 뒤로 보낸다. 이 셋은 평균·최악 O(n²)다. 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값으로 나누는 분할 정복으로 평균 O(n log n), 최악 O(n²)다. 힙 정렬과 합병(병합) 정렬은 최악에도 O(n log n)이다. 이진 검색은 정렬된 자료에서 가운데 값과 비교해 범위를 절반씩 줄이며 O(log n)이다. 해싱은 해시 함수로 키의 저장 위치(홈 주소)를 계산해 바로 접근한다.
비유로 이해하기
카드 정리를 떠올리자. 삽입 정렬은 손에 든 카드 사이에 새 카드를 끼워 넣기, 선택 정렬은 바닥에서 가장 작은 카드를 골라 순서대로 집기, 버블 정렬은 옆 카드끼리 계속 자리를 바꾸기다. 이진 검색은 사전에서 가운데를 펼쳐 앞뒤를 정하는 방법이다.
자세히
먼저 알아 둘 말
| 말 | 뜻 |
|---|---|
| 회전(패스) | 정렬 과정 한 바퀴 |
| 피벗 | 퀵 정렬에서 나누는 기준 값 |
| 분할 정복 | 문제를 작게 나눠 각각 풀고 합치는 방법 |
| 시간 복잡도 | 자료 수 n에 따라 연산 횟수가 늘어나는 정도 (Big-O 표기) |
| 힙 | 부모가 자식보다 항상 크거나(최대 힙) 작은(최소 힙) 완전 이진 트리 |
| 충돌 | 해싱에서 서로 다른 키가 같은 주소로 계산되는 것 |
정렬 알고리즘 비교
| 정렬 | 방법 | 평균 | 최악 |
|---|---|---|---|
| 삽입 | 앞의 정렬된 부분에 끼워 넣기 | O(n²) | O(n²) |
| 선택 | 최솟값을 골라 앞과 교환 | O(n²) | O(n²) |
| 버블 | 인접한 두 값 비교·교환 | O(n²) | O(n²) |
| 셸 | 간격을 두고 삽입 정렬, 간격을 줄여 감 | O(n^1.5) | O(n²) |
| 퀵 | 피벗 기준 분할 (분할 정복) | O(n log n) | O(n²) |
| 힙 | 힙 구조로 최댓값을 꺼냄 | O(n log n) | O(n log n) |
| 합병 | 반으로 나눠 정렬 후 합침 | O(n log n) | O(n log n) |
| 기수(Radix) | 자릿수별로 버킷에 분배 | O(dn) | O(dn) |
회전 과정 예 (오름차순, 5 2 4 1)
| 정렬 | 1회전 후 | 설명 |
|---|---|---|
| 삽입 | 2 5 4 1 | 2를 5 앞에 끼움 |
| 선택 | 1 2 4 5 | 최솟값 1과 첫째 5 교환 |
| 버블 | 2 4 1 5 | 5가 이웃과 바뀌며 맨 뒤로 |
Big-O 크기 순서
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). 이진 검색 O(log n), 선형 검색 O(n).
해싱
- 해시 함수: 제산법(키 mod 소수), 제곱법, 폴딩법, 기수 변환법, 숫자 분석법(계수 분석법), 무작위법
- 충돌: 다른 키가 같은 주소(동의어, Synonym). 버킷이 꽉 차면 오버플로
- 충돌 해결: 개방 주소법(선형 조사 등), 체이닝(연결 리스트로 잇기)
기출에서 더 나온 것
| 말 | 뜻 |
|---|---|
| 알고리즘 설계 기법 | 분할 정복(Divide and Conquer), 탐욕(Greedy), 동적 계획법, 백트래킹, 분기 한정법 |
| 선형 검색 | 처음부터 하나씩 비교한다. 자료가 정렬돼 있지 않아도 된다 |
| 힙 정렬 시간 | 평균·최악 모두 O(n log n) |
| 폴딩법 | 키를 여러 부분으로 나눠 더하거나 XOR한 값을 주소로 쓰는 해싱 함수 |
시험에 이렇게 나와요
- 선택·삽입·버블 정렬 회전별 결과 쓰기 → 회전마다 손으로 직접 따라가 본다
- 평균 O(n log n) → 합병·퀵·힙 정렬 (합병은 최악도 n log n, 퀵은 최악 n²)
- 퀵 정렬 → 피벗 기준으로 나눠 정복, 많은 자료 이동 없이 부분 파일로 나눈다
- 이진 검색 → 정렬된 자료의 가운데와 비교하며 반씩 줄인다 (피보나치 수열을 쓰는 것은 피보나치 검색)
- 해싱 함수 → 제산법·제곱법·폴딩법·기수 변환법·숫자 분석법 (개방 주소법은 충돌 해결 방법)
- O(1) → 입력 개수와 관계없이 수행 시간이 일정
확인 문제
Q1. 8, 3, 5, 1을 오름차순 선택 정렬할 때 1회전 후의 결과는?
- 3, 5, 1, 8
- 1, 8, 5, 3
- 1, 3, 5, 8
- 3, 8, 5, 1
정답 보기
2번 1, 8, 5, 3
선택 정렬은 회전마다 남은 것 중 최솟값을 찾아 맨 앞과 교환한다. 1회전: 최솟값 1과 첫째 8을 교환 → 1, 8, 5, 3.
Q2. 9, 6, 7, 3, 5를 오름차순 버블 정렬할 때 1회전 후의 결과는?
- 6, 7, 3, 5, 9
- 3, 5, 6, 7, 9
- 6, 9, 7, 3, 5
- 3, 6, 7, 9, 5
정답 보기
1번 6, 7, 3, 5, 9
9가 이웃과 차례로 바뀌며 맨 뒤로 간다: 6 7 3 5 9.
Q3. 최악의 경우에도 O(n log n)을 보장하는 정렬은?
- 삽입 정렬
- 퀵 정렬
- 힙 정렬
- 버블 정렬
정답 보기
3번 힙 정렬
힙·합병 정렬은 최악에도 n log n. 퀵은 최악 n².
Q4. 이진 검색에 대한 설명으로 옳은 것은?
- 가운데 값과 비교해 범위를 절반씩 줄인다
- 자료가 정렬되어 있지 않아도 된다
- 처음부터 하나씩 차례로 비교한다
- 시간 복잡도는 O(n²)이다
정답 보기
1번 가운데 값과 비교해 범위를 절반씩 줄인다
정렬된 자료가 전제이고 O(log n).
Q5. 해싱에서 키 값을 소수로 나눈 나머지를 주소로 쓰는 방법은?
- 제곱법
- 제산법
- 폴딩법
- 기수 변환법
정답 보기
2번 제산법
제산법이다. 폴딩법은 키를 여러 부분으로 나눠 더하고, 제곱법은 키를 제곱한 값의 가운데를 쓴다.
헷갈리기 쉬운 O·X
퀵 정렬은 최악의 경우에도 항상 O(n log n)이다.
정답 보기
X 피벗이 치우치면 O(n²).
선택 정렬은 회전마다 남은 값 중 최솟값을 찾아 앞쪽과 교환한다.
정답 보기
O
해싱에서 서로 다른 키가 같은 주소로 계산되는 것을 충돌이라 한다.
정답 보기
O 그 키들을 동의어라 부른다.