개념
데이터를 특정 순서대로 나열하는 알고리즘
오름차순, 내림차순 등 원하는 기준으로 데이터를 정렬
정렬 알고리즘 비교
| 알고리즘 | 최선 | 평균 | 최악 | 공간복잡도 | 안정성 |
|---|---|---|---|---|---|
| 버블 정렬 | 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 log n) | O(n) | 안정 |
| 퀵 정렬 | 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(1) | 불안정 |
Python 내장 정렬
1. sort() vs sorted()
# sort() - 원본 리스트를 정렬 (반환값 None)
arr = [3, 1, 4, 1, 5]
arr.sort()
print(arr) # [1, 1, 3, 4, 5]
# sorted() - 새로운 정렬된 리스트 반환
arr = [3, 1, 4, 1, 5]
sorted_arr = sorted(arr)
print(sorted_arr) # [1, 1, 3, 4, 5]
print(arr) # [3, 1, 4, 1, 5] (원본 유지)
# 시간복잡도: O(n log n) - Timsort 사용2. 다양한 정렬 옵션
# 내림차순
arr = [3, 1, 4, 1, 5]
arr.sort(reverse=True)
print(arr) # [5, 4, 3, 1, 1]
# key 함수로 정렬 기준 지정
words = ['banana', 'pie', 'Washington', 'book']
# 길이순 정렬
words.sort(key=len)
print(words) # ['pie', 'book', 'banana', 'Washington']
# 대소문자 무시 정렬
words.sort(key=str.lower)
print(words) # ['banana', 'book', 'pie', 'Washington']
# 튜플 리스트 정렬
students = [('Alice', 85), ('Bob', 75), ('Charlie', 90)]
# 점수로 정렬
students.sort(key=lambda x: x[1])
print(students) # [('Bob', 75), ('Alice', 85), ('Charlie', 90)]
# 여러 기준으로 정렬 (나이 먼저, 같으면 이름)
people = [('Alice', 30), ('Bob', 25), ('Charlie', 30)]
people.sort(key=lambda x: (x[1], x[0]))
print(people) # [('Bob', 25), ('Alice', 30), ('Charlie', 30)]기본 정렬 알고리즘
1. 버블 정렬 (Bubble Sort)
인접한 두 요소를 비교하여 교환하는 방식
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
# 마지막 i개는 이미 정렬됨
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 교환이 없으면 이미 정렬됨
if not swapped:
break
return arr
# 테스트
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]
# 시간복잡도: O(n²)
# 공간복잡도: O(1)
# 안정 정렬특징: 간단하지만 느림, 거의 정렬된 데이터에 유리
2. 선택 정렬 (Selection Sort)
최솟값을 찾아 맨 앞과 교환하는 방식
def selection_sort(arr):
n = len(arr)
for i in range(n):
# 최솟값의 인덱스 찾기
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 최솟값을 맨 앞으로 이동
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 테스트
print(selection_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]
# 시간복잡도: O(n²)
# 공간복잡도: O(1)
# 불안정 정렬특징: 교환 횟수가 적음, 항상 O(n²)
3. 삽입 정렬 (Insertion Sort)
각 요소를 적절한 위치에 삽입하는 방식
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# key보다 큰 요소들을 오른쪽으로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 테스트
print(insertion_sort([12, 11, 13, 5, 6]))
# [5, 6, 11, 12, 13]
# 시간복잡도: O(n²) - 최선 O(n)
# 공간복잡도: O(1)
# 안정 정렬특징: 거의 정렬된 데이터에 매우 효율적, 작은 데이터에 유리
고급 정렬 알고리즘
4. 병합 정렬 (Merge Sort)
분할 정복 방식으로 배열을 나누고 합치며 정렬
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 분할
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 병합
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# 두 배열을 비교하며 병합
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 남은 요소 추가
result.extend(left[i:])
result.extend(right[j:])
return result
# 테스트
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]
# 시간복잡도: O(n log n) - 항상 보장
# 공간복잡도: O(n)
# 안정 정렬특징: 안정적인 O(n log n), 추가 메모리 필요
5. 퀵 정렬 (Quick Sort)
피벗을 기준으로 작은 값과 큰 값을 나누어 정렬
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 제자리 정렬 버전
def quick_sort_inplace(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 테스트
print(quick_sort([10, 7, 8, 9, 1, 5]))
# [1, 5, 7, 8, 9, 10]
arr = [10, 7, 8, 9, 1, 5]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr) # [1, 5, 7, 8, 9, 10]
# 시간복잡도: 평균 O(n log n), 최악 O(n²)
# 공간복잡도: O(log n)
# 불안정 정렬특징: 평균적으로 가장 빠름, 피벗 선택이 중요
자주 나오는 문제 유형
1. K번째 큰 수 찾기
문제: 정렬되지 않은 배열에서 K번째로 큰 수 찾기
import heapq
def find_kth_largest(nums, k):
# 방법 1: 정렬 사용
return sorted(nums, reverse=True)[k - 1]
# 방법 2: 힙 사용 (더 효율적)
# return heapq.nlargest(k, nums)[k - 1]
# 방법 3: 최소 힙 사용 (공간 O(k))
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 테스트
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
# 시간복잡도: O(n log n) 정렬, O(n log k) 힙
# 공간복잡도: O(k)핵심: 전체 정렬 vs 부분 정렬 선택
2. 색깔별 정렬 (Sort Colors)
문제: 0, 1, 2로만 이루어진 배열을 정렬 (Dutch National Flag)
def sort_colors(nums):
# 투 포인터 (three-way partitioning)
low = mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
# 테스트
print(sort_colors([2, 0, 2, 1, 1, 0])) # [0, 0, 1, 1, 2, 2]
# 시간복잡도: O(n)
# 공간복잡도: O(1)핵심: 한 번의 순회로 O(n) 정렬
3. 배열 합병 (Merge Sorted Array)
문제: 정렬된 두 배열을 하나로 합치기
def merge_sorted_arrays(nums1, m, nums2, n):
# 뒤에서부터 채우기
p1 = m - 1
p2 = n - 1
p = m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# nums2의 남은 요소 복사
nums1[:p2 + 1] = nums2[:p2 + 1]
return nums1
# 테스트
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
print(merge_sorted_arrays(nums1, 3, nums2, 3))
# [1, 2, 2, 3, 5, 6]
# 시간복잡도: O(m + n)
# 공간복잡도: O(1)핵심: 뒤에서부터 채워 공간복잡도 O(1)
4. 회의실 배정 (Meeting Rooms)
문제: 회의 시간이 겹치지 않는지 확인
def can_attend_meetings(intervals):
# 시작 시간 기준 정렬
intervals.sort(key=lambda x: x[0])
# 겹치는지 확인
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False
return True
# 테스트
print(can_attend_meetings([[0, 30], [5, 10], [15, 20]])) # False
print(can_attend_meetings([[7, 10], [2, 4]])) # True
# 시간복잡도: O(n log n)
# 공간복잡도: O(1)핵심: 정렬 후 순차 비교
5. 최소 회의실 개수
문제: 모든 회의를 진행하기 위한 최소 회의실 개수
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
# 시작 시간 기준 정렬
intervals.sort(key=lambda x: x[0])
# 최소 힙 (종료 시간 저장)
heap = []
heapq.heappush(heap, intervals[0][1])
for i in range(1, len(intervals)):
# 가장 빨리 끝나는 회의가 현재 회의 시작 전에 끝나면
if heap[0] <= intervals[i][0]:
heapq.heappop(heap)
heapq.heappush(heap, intervals[i][1])
return len(heap)
# 테스트
print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]])) # 2
# 시간복잡도: O(n log n)
# 공간복잡도: O(n)핵심: 힙으로 종료 시간 관리
추천 연습 문제
기초
중급
고급
핵심 요약
| 알고리즘 | 시간복잡도 | 공간복잡도 | 사용 시기 |
|---|---|---|---|
| 버블/선택 | O(n²) | O(1) | 작은 데이터, 교육용 |
| 삽입 | O(n²) | O(1) | 거의 정렬된 데이터 |
| 병합 | O(n log n) | O(n) | 안정 정렬 필요 시 |
| 퀵 | O(n log n) | O(log n) | 평균적으로 가장 빠름 |
| Python 내장 | O(n log n) | O(n) | 실전에서 사용 |
정렬 선택 가이드
-
Python 내장 정렬 사용
- 대부분의 경우
sort()또는sorted()사용 - Timsort 알고리즘 (병합 + 삽입)
- 대부분의 경우
-
직접 구현이 필요한 경우
- 특수한 비교 로직
- 공간복잡도 제약
- 알고리즘 이해를 위한 학습
-
부분 정렬만 필요한 경우
- 힙 사용 (
heapq.nlargest,heapq.nsmallest)
- 힙 사용 (