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

알고리즘·자료구조 출제 경향

정보처리기사에서 알고리즘과 자료구조는 매 시험 10문제 안팎으로 출제되는 핵심 파트입니다. 정렬 알고리즘의 시간복잡도 비교, 스택·큐·트리의 특성과 응용이 자주 나옵니다. 암기보다 원리 이해가 훨씬 효율적입니다.

【기출 토픽 1】 정렬 알고리즘 시간복잡도

기출 문제 예시: 다음 정렬 알고리즘 중 최악의 경우(Worst Case) 시간복잡도가 O(n²)인 것만 묶인 것은?

• ① 퀵 정렬, 병합 정렬
• ② 버블 정렬, 삽입 정렬, 선택 정렬 ✅
• ③ 힙 정렬, 병합 정렬
• ④ 퀵 정렬, 삽입 정렬

해설: 버블·삽입·선택 정렬은 평균·최악 모두 O(n²)입니다. 퀵 정렬은 평균 O(n log n)이지만 최악(이미 정렬된 배열)은 O(n²)입니다. 병합 정렬과 힙 정렬은 항상 O(n log n)을 보장합니다.

정렬 알고리즘 복잡도 비교표:

• 버블/선택/삽입: 평균 O(n²), 최악 O(n²), 안정 정렬(삽입·버블만)
• 퀵 정렬: 평균 O(n log n), 최악 O(n²), 불안정 정렬
• 병합 정렬: 항상 O(n log n), 안정 정렬, 추가 메모리 O(n)
• 힙 정렬: 항상 O(n log n), 불안정 정렬, 제자리 정렬

【기출 토픽 2】 스택(Stack)의 특성과 응용

기출 문제 예시: 스택을 이용하여 후위 표기식(Postfix)으로 변환하거나 계산하는 문제가 자주 출제됩니다. 중위 표기식 A+B*C를 후위 표기식으로 변환하면?

• ① ABC*+ ✅
• ② +A*BC
• ③ A+BC*
• ④ ABC+*

해설: 연산자 우선순위: *(곱셈) > +(덧셈). B*C를 먼저 계산한 뒤 A와 더하므로 후위 표기는 A B C * +입니다. 스택은 LIFO(Last In First Out) 구조로, 함수 호출 스택, 괄호 검사, 후위 표기식 변환에 활용됩니다.

【기출 토픽 3】 큐(Queue)와 덱(Deque)

기출 문제 예시: FIFO(First In First Out) 구조로 운영체제의 프로세스 스케줄링, 프린터 대기열 등에 사용되는 자료구조는?

• ① 스택
• ② 큐 ✅
• ③ 트리
• ④ 그래프

해설: 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조입니다. 원형 큐(Circular Queue)는 배열의 끝과 처음을 연결해 메모리를 효율적으로 사용합니다. 덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입·삭제가 가능합니다.

【기출 토픽 4】 이진 트리와 순회

기출 문제 예시: 이진 트리를 루트 → 왼쪽 자식 → 오른쪽 자식 순서로 방문하는 순회 방법은?

• ① 중위 순회 (Inorder)
• ② 전위 순회 (Preorder) ✅
• ③ 후위 순회 (Postorder)
• ④ 레벨 순회

해설:

• 전위(Preorder): 루트 → 왼쪽 → 오른쪽
• 중위(Inorder): 왼쪽 → 루트 → 오른쪽 (이진 탐색 트리에서 정렬된 순서 출력)
• 후위(Postorder): 왼쪽 → 오른쪽 → 루트 (폴더 삭제 등에 활용)

알고리즘·자료구조 최종 정리

정렬 알고리즘의 시간복잡도 표를 암기하고, 스택·큐·트리의 동작 원리와 대표 응용 사례를 연결 지어 학습하세요. 후위 표기식 변환 문제는 반드시 직접 손으로 풀어보는 연습이 필요합니다.