정보처리기사 알고리즘 정렬 탐색 영역은 2과목 소프트웨어개발에서 빠지지 않는 단골 출제 파트입니다. 이번 1회차에서는 버블 정렬·선택 정렬·삽입 정렬의 동작 원리와 시간 복잡도, 그리고 순차 탐색·이진 탐색의 특성을 집중적으로 학습합니다.
본 회차 안내
2과목 소프트웨어개발 – 알고리즘 (정렬/탐색, 복잡도) (1/2회차)
문제 1. 버블 정렬의 시간 복잡도
버블 정렬(Bubble Sort)은 인접한 두 원소를 반복적으로 비교하고 교환하여 정렬을 수행합니다. 데이터가 n개일 때, 버블 정렬의 최악·평균 시간 복잡도로 올바른 것은?
- O(n)
- O(n log n)
- O(n²)
- O(log n)
정답
③ O(n²) — 버블 정렬은 최악·평균 모두 O(n²)의 시간 복잡도를 가집니다.
해설
버블 정렬은 바깥쪽 루프 n-1회, 안쪽 루프 최대 n-1회를 수행합니다. 따라서 비교 횟수는 (n-1)+(n-2)+…+1 = n(n-1)/2로 O(n²)이 됩니다. 이미 정렬된 경우에만 최선 O(n)이 가능합니다(조기 종료 조건 적용 시).
오답: ① O(n) — 선형 탐색이나 조기 종료가 보장된 특수한 경우에만 해당하며 일반적인 버블 정렬의 복잡도가 아닙니다.
오답: ② O(n log n) — 병합 정렬(Merge Sort)이나 힙 정렬(Heap Sort)의 시간 복잡도이며 버블 정렬과 무관합니다.
정답: ③ O(n²) — 두 개의 중첩 반복문으로 인해 비교 횟수가 n²에 비례하므로 올바른 답입니다.
오답: ④ O(log n) — 이진 탐색처럼 매 단계마다 탐색 범위를 절반씩 줄이는 알고리즘의 복잡도로, 버블 정렬과 관계없습니다.
문제 2. 선택 정렬의 동작 원리
선택 정렬(Selection Sort)에 대한 설명으로 가장 옳은 것은?
- 매 단계마다 현재 미정렬 구간에서 최솟값을 찾아 맨 앞 원소와 교환한다.
- 인접한 두 원소를 비교하여 순서가 맞지 않으면 교환을 반복한다.
- 피벗(pivot)을 기준으로 작은 값과 큰 값을 분리한 후 재귀적으로 정렬한다.
- 정렬된 부분 배열에 새 원소를 올바른 위치에 삽입하는 방식으로 동작한다.
정답
① 매 단계마다 최솟값을 찾아 맨 앞 원소와 교환한다 — 선택 정렬의 핵심 동작입니다.
해설
선택 정렬은 전체 배열에서 최솟값을 찾아 첫 번째 위치와 교환하고, 다음에는 나머지 구간에서 최솟값을 찾아 두 번째 위치와 교환하는 과정을 반복합니다. 교환 횟수는 최대 n-1회로 다른 정렬보다 교환 비용이 낮습니다. 그러나 비교 횟수는 항상 O(n²)입니다.
정답: ① 미정렬 구간에서 최솟값을 선택해 앞과 교환하는 방식이 선택 정렬의 정확한 설명입니다.
오답: ② 인접 원소를 반복 비교·교환하는 방식은 버블 정렬(Bubble Sort)의 특징입니다.
오답: ③ 피벗을 기준으로 분할 후 재귀 정렬하는 방식은 퀵 정렬(Quick Sort)의 동작 원리입니다.
오답: ④ 정렬된 부분 배열에 새 원소를 삽입하는 방식은 삽입 정렬(Insertion Sort)의 동작 원리입니다.
문제 3. 이진 탐색의 전제 조건
이진 탐색(Binary Search)을 사용하기 위한 필수 전제 조건으로 올바른 것은? 단, 이진 탐색은 반복적으로 탐색 범위를 절반으로 줄여가는 알고리즘입니다.
- 데이터가 연결 리스트(Linked List) 구조로 저장되어 있어야 한다.
- 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야 한다.
- 데이터의 개수가 반드시 짝수여야 한다.
- 데이터가 해시 테이블(Hash Table)에 저장되어 있어야 한다.
정답
② 데이터가 정렬되어 있어야 한다 — 이진 탐색은 정렬된 배열에서만 올바르게 동작합니다.
해설
이진 탐색은 중간값과 탐색 키를 비교하여 탐색 범위를 절반씩 줄여 나갑니다. 이 과정이 정확하려면 데이터가 정렬되어 있어야 합니다. 정렬 여부에 따라 중간값 비교만으로 탐색 방향을 결정할 수 있기 때문입니다. 이진 탐색의 시간 복잡도는 O(log n)입니다.
오답: ① 연결 리스트는 임의 접근(Random Access)이 불가능하여 이진 탐색에 적합하지 않습니다. 이진 탐색은 배열처럼 인덱스 접근이 가능한 구조가 필요합니다.
정답: ② 데이터가 정렬되어 있어야만 중간 원소 비교 결과로 탐색 범위를 올바르게 좁힐 수 있습니다.
오답: ③ 데이터 개수가 짝수일 필요는 없습니다. 홀수 개의 데이터에서도 이진 탐색은 정상적으로 동작합니다.
오답: ④ 해시 테이블은 해시 함수를 이용한 탐색 구조로, 이진 탐색과는 전혀 다른 탐색 방법입니다.
문제 4. 삽입 정렬의 최선 시간 복잡도
삽입 정렬(Insertion Sort)은 이미 정렬된 부분 배열에 새 원소를 적절한 위치에 삽입하며 정렬을 완성합니다. 입력 데이터가 이미 오름차순으로 완전히 정렬되어 있을 때, 삽입 정렬의 시간 복잡도로 올바른 것은?
- O(n²)
- O(n log n)
- O(n)
- O(1)
정답
③ O(n) — 데이터가 이미 정렬된 최선의 경우, 삽입 정렬은 각 원소를 한 번씩만 비교하면 됩니다.
해설
삽입 정렬은 새 원소를 삽입할 위치를 찾기 위해 이미 정렬된 구간을 역방향으로 스캔합니다. 입력이 이미 정렬되어 있으면 각 원소가 바로 앞 원소보다 크므로, 단 한 번의 비교만으로 삽입 위치가 결정됩니다. 따라서 전체 비교 횟수는 n-1번이 되어 O(n)이 성립합니다.
오답: ① O(n²) — 역순 정렬처럼 최악의 경우 삽입 위치를 찾기 위해 매번 전체 정렬 구간을 스캔해야 할 때의 복잡도입니다.
오답: ② O(n log n) — 병합 정렬이나 힙 정렬의 평균·최악 시간 복잡도이며 삽입 정렬 최선 시나리오와 무관합니다.
정답: ③ O(n) — 이미 정렬된 배열에서는 각 단계마다 비교를 1회만 수행하므로 총 n-1회 비교, 즉 O(n)이 됩니다.
오답: ④ O(1) — 상수 시간으로 모든 원소를 정렬할 수는 없습니다. O(1)은 원소 접근이나 단일 연산에 해당하는 복잡도입니다.
문제 5. 순차 탐색과 이진 탐색 비교
순차 탐색(Sequential Search)과 이진 탐색(Binary Search)에 대한 설명으로 옳지 않은 것은?
- 순차 탐색은 정렬되지 않은 데이터에서도 사용할 수 있다.
- 이진 탐색의 평균 시간 복잡도는 O(log n)이다.
- 순차 탐색의 최악 시간 복잡도는 O(n)이다.
- 이진 탐색은 정렬 여부와 관계없이 항상 순차 탐색보다 빠르다.
정답
④ “이진 탐색은 정렬 여부와 관계없이 항상 순차 탐색보다 빠르다”는 설명은 옳지 않습니다.
해설
이진 탐색은 반드시 데이터가 정렬되어 있어야 사용할 수 있습니다. 정렬되지 않은 데이터에서는 이진 탐색을 적용할 수 없으며, 이 경우 순차 탐색만 사용 가능합니다. 따라서 “정렬 여부와 관계없이 항상 빠르다”는 표현은 틀린 설명입니다.
오답: ① 순차 탐색은 처음부터 끝까지 하나씩 확인하므로 정렬 여부와 무관하게 적용 가능합니다. 올바른 설명이므로 정답이 아닙니다.
오답: ② 이진 탐색은 탐색 범위를 매 단계 절반으로 줄이므로 평균·최악 시간 복잡도가 O(log n)입니다. 올바른 설명이므로 정답이 아닙니다.
오답: ③ 순차 탐색은 탐색 키가 마지막 원소이거나 존재하지 않을 때 모든 n개의 원소를 검사해야 하므로 최악 복잡도는 O(n)입니다. 올바른 설명이므로 정답이 아닙니다.
정답: ④ 이진 탐색은 정렬된 데이터에서만 동작합니다. 정렬되지 않은 상태에서는 이진 탐색을 사용할 수 없으므로 “항상 빠르다”는 설명은 틀렸습니다.
학습 정리
이번 회차에서는 정보처리기사 알고리즘 정렬 탐색 영역의 핵심 세 가지를 학습했습니다. 첫째, 버블·선택·삽입 정렬의 시간 복잡도(최선·평균·최악)를 구분할 수 있어야 합니다. 둘째, 이진 탐색은 반드시 정렬된 데이터를 전제로 하며 O(log n)의 효율을 제공합니다. 따라서 각 알고리즘의 특성과 적용 조건을 함께 기억하는 것이 실전 시험 대비의 핵심입니다.