자료구조 기본 개념
자료구조는 데이터를 효율적으로 저장·관리하는 구조입니다. 정보처리기사에서는 각 자료구조의 특징과 시간복잡도, 적용 사례가 자주 출제됩니다.
선형 자료구조
스택 (Stack)
- LIFO(Last In First Out): 마지막에 넣은 데이터가 먼저 나옴
- 연산: push(삽입), pop(삭제), peek(최상단 조회)
- 활용: 함수 호출 스택, 괄호 검사, 후위 표기식 계산, 브라우저 뒤로가기
큐 (Queue)
- FIFO(First In First Out): 먼저 넣은 데이터가 먼저 나옴
- 연산: enqueue(삽입), dequeue(삭제)
- 활용: 프로세스 스케줄링, 프린터 스풀, BFS 탐색
덱 (Deque, Double-Ended Queue)
양쪽 끝에서 삽입·삭제 모두 가능한 큐
비선형 자료구조
트리 (Tree)
- 이진트리: 각 노드가 최대 2개의 자식
- 완전 이진트리: 마지막 레벨을 제외하고 모두 채워진 트리
- 이진 탐색 트리(BST): 왼쪽 자식
- AVL 트리: 균형 이진 탐색 트리, 높이 차 최대 1
- 힙(Heap): 최대/최소값 빠르게 찾기 위한 완전 이진트리
트리 순회 방법
- 전위 순회(Pre-order): 루트 → 왼쪽 → 오른쪽
- 중위 순회(In-order): 왼쪽 → 루트 → 오른쪽 (BST에서 오름차순 출력)
- 후위 순회(Post-order): 왼쪽 → 오른쪽 → 루트
정렬 알고리즘
시간복잡도 비교
- 버블/선택/삽입 정렬: O(n²) – 단순하지만 느림
- 합병 정렬(Merge Sort): O(n log n), 안정 정렬, 추가 메모리 필요
- 퀵 정렬(Quick Sort): 평균 O(n log n), 최악 O(n²), 실제로 가장 빠름
- 힙 정렬(Heap Sort): O(n log n), 추가 메모리 불필요
- 계수 정렬(Counting Sort): O(n+k), 데이터 범위 제한 시 선형 시간
안정 정렬 vs 불안정 정렬
- 안정 정렬: 동일 키 값의 원소 순서 유지 (삽입, 합병, 버블 정렬)
- 불안정 정렬: 동일 키 값의 순서 보장 안 함 (퀵, 힙, 선택 정렬)
탐색 알고리즘
- 순차 탐색: O(n), 정렬 불필요
- 이진 탐색: O(log n), 반드시 정렬된 배열 필요
- DFS(깊이 우선 탐색): 스택 또는 재귀, 경로 탐색에 유리
- BFS(너비 우선 탐색): 큐 사용, 최단 경로 탐색에 유리
시간복잡도 Big-O 정리
- O(1)
- 스택/큐 push·pop: O(1)
- BST 탐색: 평균 O(log n), 최악 O(n) (편향 트리)
마무리
알고리즘은 시간복잡도 표를 암기하고, 각 정렬 알고리즘의 동작 원리를 이해하면 문제 풀이가 쉬워집니다. 특히 퀵/합병/힙 정렬 시간복잡도는 단골 출제 포인트입니다.