정보처리기사 기출문제 총정리 ⑮ 알고리즘·자료구조 – 정렬·탐색·스택·큐·트리

자료구조 기본 개념

자료구조는 데이터를 효율적으로 저장·관리하는 구조입니다. 정보처리기사에서는 각 자료구조의 특징과 시간복잡도, 적용 사례가 자주 출제됩니다.

선형 자료구조

스택 (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): 왼쪽 자식 < 부모 < 오른쪽 자식, 탐색 O(log n)
• 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) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
• 스택/큐 push·pop: O(1)
• BST 탐색: 평균 O(log n), 최악 O(n) (편향 트리)

마무리

알고리즘은 시간복잡도 표를 암기하고, 각 정렬 알고리즘의 동작 원리를 이해하면 문제 풀이가 쉬워집니다. 특히 퀵/합병/힙 정렬 시간복잡도는 단골 출제 포인트입니다.

정렬·탐색 알고리즘 복잡도를 한 표로 외우는 법

시험에서 가장 자주 묻는 것은 알고리즘별 시간 복잡도와 안정성입니다. 버블·선택·삽입 정렬은 평균 O(n²)이고, 병합·힙 정렬은 최악에도 O(n log n), 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)입니다.

안정 정렬은 같은 키를 가진 원소의 상대적 순서가 유지되는 정렬입니다. 버블·삽입·병합은 안정, 선택·힙·퀵은 일반 구현에서 불안정합니다. 삽입 정렬은 거의 정렬된 데이터에서 O(n)에 가까워 작은 데이터와 병합 정렬의 보조에 쓰입니다.

• 탐색: 선형 탐색 O(n), 이진 탐색 O(log n)(정렬된 배열 전제), 해시 탐색 평균 O(1).
• 자료구조: 스택은 LIFO(함수 호출, 괄호 검사), 큐는 FIFO(작업 대기열, BFS), 덱, 우선순위 큐(힙).
• 트리: 이진 탐색 트리는 편향되면 O(n)이 되므로 AVL·레드블랙 같은 균형 트리가 높이를 유지합니다. 순회는 전위·중위·후위·레벨 순서.
• 공간 복잡도: 병합 정렬은 O(n) 추가 공간, 퀵·힙은 제자리(in-place).
• 실무 감각: 라이브러리 정렬은 대개 팀소트 같은 혼합 알고리즘이므로 직접 구현보다 표준 함수를 씁니다.

※ 이 글은 학습·참고용 정리입니다. 제품 사양과 표준 개정 사항은 공식 문서에서 최신 내용을 확인하세요.