자료구조·알고리즘 복잡도 정리
탐색·정렬·트리·그래프의 대표 복잡도와 선택 기준을 정리합니다.
관련 시험 9급 컴퓨터일반정보처리기사
복잡도 해석
빅오 표기법은 입력 크기가 커질 때 증가율의 상한을 중심으로 비교합니다. 상수와 낮은 차수 항을 제거하되, 입력 특성과 평균·최악 조건을 함께 확인해야 합니다.
- 이진 탐색은 정렬된 배열에서 O(log n)이다.
- 해시 탐색은 평균 O(1)이지만 충돌에 따라 달라진다.
- 중첩 반복문의 범위가 종속되면 단순히 차수를 곱하지 않는다.
정렬 비교
퀵 정렬은 평균적으로 빠르지만 피벗 분할이 치우치면 최악 O(n²), 병합 정렬은 O(n log n)을 보장하지만 추가 메모리가 필요합니다. 힙 정렬도 O(n log n)을 보장합니다.
- 삽입 정렬은 거의 정렬된 자료에 유리하다.
- 병합 정렬은 안정 정렬이다.
- 선택 정렬은 교환 횟수가 비교적 적다.
트리와 그래프
이진 탐색 트리는 왼쪽이 작고 오른쪽이 큰 순서 관계를 사용합니다. BFS는 큐, DFS는 스택 또는 재귀를 사용하며 최단 경로 조건을 구분해야 합니다.
- 가중치가 없는 그래프의 최소 간선 경로에는 BFS가 적합하다.
- 최소 신장 트리는 모든 정점을 사이클 없이 연결한다.
- 균형이 무너지면 이진 탐색 트리의 탐색이 O(n)이 될 수 있다.
코드에서 연산 횟수를 직접 세는 기준
복잡도는 반복문 개수만 보고 정하지 말고 각 반복문의 실행 범위가 입력 n에 어떻게 의존하는지 합이나 곱으로 계산해야 합니다. 반복 변수가 매번 두 배가 되거나 절반이 되면 로그, 모든 원소 쌍을 비교하면 대체로 제곱 차수가 나타납니다.
- 연속된 반복문은 복잡도를 더하고 중첩된 독립 반복문은 곱한다.
- 재귀식 T(n)=2T(n/2)+n은 병합 정렬처럼 O(n log n)으로 해석된다.
- 그래프 탐색은 인접 리스트 기준 BFS·DFS 모두 O(V+E)이다.
탐욕법·동적계획법·최단경로 구분
탐욕법은 매 단계의 국소 최적 선택이 전체 최적해를 만든다는 성질이 증명될 때 사용하고, 동적계획법은 겹치는 부분 문제와 최적 부분 구조를 이용해 계산 결과를 재사용합니다. 그래프에서는 간선 가중치의 음수 여부에 따라 최단경로 알고리즘을 선택해야 합니다.
- 다익스트라는 음수 가중치 간선이 있으면 일반적으로 사용할 수 없다.
- 벨만-포드는 음수 간선을 처리하고 음수 사이클도 탐지할 수 있다.
- 플로이드-워셜은 모든 정점 쌍 최단경로를 O(V³)에 구한다.
- 백트래킹은 유망하지 않은 선택을 가지치기하고 분할정복은 독립된 부분 문제를 나눠 해결한다.
선형 구조·트리·그래프 연산 완성
자료구조 문제는 저장 형태와 허용 연산을 함께 봅니다. 스택은 한쪽 끝 LIFO, 큐는 삽입과 삭제 끝이 다른 FIFO이며, 트리는 루트·부모·자식·높이 관계, 그래프는 방향·가중치와 표현 방식에 따라 탐색·복잡도가 달라집니다.
- 원형 큐는 front와 rear의 나머지 연산을 사용하며 한 칸을 비우는 구현에서는 포화 조건을 별도로 계산한다.
- 전위는 루트-왼쪽-오른쪽, 중위는 왼쪽-루트-오른쪽, 후위는 왼쪽-오른쪽-루트 순회다.
- AVL 트리는 각 노드의 왼쪽·오른쪽 서브트리 높이 차를 제한하고 회전으로 균형을 복구한다.
- 인접 행렬은 공간 O(V²)로 간선 확인이 빠르고 인접 리스트는 희소 그래프에서 O(V+E) 공간에 유리하다.
- Kruskal은 간선을 가중치 순으로 선택하며 사이클을 막고, Prim은 현재 트리에서 바깥 정점으로 나가는 최소 간선을 확장한다.
시험에 바로 쓰는 비교표
| 구조·알고리즘 | 평균 | 최악 | 필수 조건·특징 |
|---|---|---|---|
| 이진 탐색 | O(log n) | O(log n) | 정렬된 임의 접근 자료 |
| 균형 BST 탐색 | O(log n) | O(log n) | 트리 높이를 로그 수준으로 유지 |
| 일반 BST 탐색 | O(log n) | O(n) | 삽입 순서에 따라 편향 가능 |
| 해시 탐색 | O(1) | O(n) | 충돌 처리와 해시 함수 품질 영향 |
지문 표현을 판단 기준으로 바꾸기
- 왼쪽 키는 작고 오른쪽 키는 크다 → 이진 탐색 트리
- 가중치 없는 최소 간선 경로 → BFS
- 피벗 분할이 한쪽으로 치우친다 → 퀵 정렬 최악 O(n²)
자주 틀리는 판단
- 퀵 정렬의 최악 복잡도를 O(n log n)으로 단정
- BFS와 DFS의 자료구조를 반대로 암기
- 안정 정렬과 제자리 정렬을 같은 개념으로 판단
개념을 확인했다면 실제 문제에서 판단 기준을 적용해보세요.
분야별 문제 풀기