알고리즘¶
1. 시간/공간 복잡도¶
Big-O 표기법¶
알고리즘의 최악의 경우 성능을 표현합니다.
| 표기 | 이름 | 예시 |
|---|---|---|
| O(1) | 상수 | 배열 인덱스 접근 |
| O(log n) | 로그 | 이진 탐색 |
| O(n) | 선형 | 선형 탐색 |
| O(n log n) | 선형로그 | 퀵/병합/힙 정렬 |
| O(n²) | 제곱 | 버블/선택/삽입 정렬 |
| O(2ⁿ) | 지수 | 피보나치(재귀) |
성능 순서: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
2. 정렬 알고리즘¶
비교¶
| 알고리즘 | 평균 | 최악 | 공간 | 안정 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | O |
| 선택 정렬 | O(n²) | O(n²) | O(1) | X |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | O |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | X |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | O |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | X |
안정 정렬: 같은 값의 원소가 정렬 후에도 원래 순서를 유지
버블 정렬 (Bubble Sort)¶
인접한 두 원소를 비교하여 필요시 교환합니다.
선택 정렬 (Selection Sort)¶
최솟값을 찾아 맨 앞에 배치합니다. 교환 횟수가 최소입니다.
삽입 정렬 (Insertion Sort)¶
정렬된 부분에 새 원소를 끼워넣습니다. 이미 정렬된 배열에 효율적입니다.
퀵 정렬 (Quick Sort)¶
피벗을 기준으로 분할 정복합니다. 실무에서 가장 많이 사용합니다.
- 피벗보다 작은 값 → 왼쪽
- 피벗보다 큰 값 → 오른쪽
- 최악의 경우: 이미 정렬된 배열 + 맨 끝 피벗 선택 → O(n²)
병합 정렬 (Merge Sort)¶
반으로 나누고 → 정렬하고 → 병합합니다. 추가 메모리 O(n)이 필요합니다.
3. 탐색 알고리즘¶
선형 탐색 (Linear Search)¶
처음부터 끝까지 순서대로 탐색합니다.
- 시간복잡도: O(n)
- 정렬 불필요
이진 탐색 (Binary Search)¶
정렬된 배열에서 중간값과 비교하며 범위를 절반씩 줄입니다.
- 시간복잡도: O(log n)
- 반드시 정렬된 배열에서만 사용 가능
[1, 3, 5, 7, 9, 11, 13] → 7 탐색
중간값: 7 → 일치! 탐색 성공
[1, 3, 5, 7, 9, 11, 13] → 11 탐색
중간값: 7 → 11 > 7이므로 오른쪽 탐색
중간값: 11 → 일치!
4. 그래프 탐색¶
DFS (깊이 우선 탐색)¶
스택(또는 재귀)을 사용합니다. 한 방향으로 끝까지 탐색 후 되돌아옵니다.
BFS (너비 우선 탐색)¶
큐를 사용합니다. 가까운 노드부터 탐색합니다. 최단 경로 탐색에 활용합니다.
최단 경로 알고리즘¶
| 알고리즘 | 음수 가중치 | 시간복잡도 | 용도 |
|---|---|---|---|
| 다익스트라 | X | O(n²) | 단일 출발점 |
| 벨만-포드 | O | O(VE) | 음수 가중치 허용 |
| 플로이드-워셜 | O | O(n³) | 모든 쌍 최단경로 |
시험 포인트¶
- 각 정렬 알고리즘의 시간복잡도 암기 필수
- 안정 정렬 여부 (버블, 삽입, 병합 → 안정 / 선택, 퀵, 힙 → 불안정)
- 퀵 정렬의 최악 경우: 이미 정렬된 배열
- 이진 탐색은 정렬된 배열에서만 사용 가능
- BFS → 최단 경로, DFS → 경로 존재 여부