정보처리기사 알고리즘 복잡도 학습의 2회차에서는 탐색 알고리즘의 동작 원리와 공간 복잡도, 고급 탐색 기법을 다룹니다. 1회차에서 기본 정렬 시간 복잡도를 익혔다면, 이번 회차에서는 탐색 심화와 복잡도 분석을 함께 이해할 수 있습니다.
본 회차 안내
2과목 소프트웨어개발 – 알고리즘 (정렬/탐색, 복잡도) (2/2회차)
문제 1. 이진 탐색의 전제 조건
이진 탐색(Binary Search)은 특정 조건이 만족될 때만 올바르게 동작합니다. 다음 중 이진 탐색을 적용하기 위해 반드시 필요한 전제 조건으로 가장 적절한 것은?
- 탐색 대상 데이터가 연결 리스트(Linked List)로 구성되어 있어야 한다.
- 탐색 대상 데이터가 정렬된 상태여야 한다.
- 탐색 대상 데이터의 원소 개수가 짝수여야 한다.
- 탐색 대상 데이터에 중복 값이 없어야 한다.
정답
② 탐색 대상 데이터가 정렬된 상태여야 한다.
해설
이진 탐색은 배열의 중간 값과 목표 값을 비교하여 탐색 범위를 절반으로 줄이는 방식입니다. 이 과정이 올바르려면 데이터가 정렬되어 있어야 대소 비교로 방향을 결정할 수 있습니다. 정렬 없이는 중간 값 비교 결과가 탐색 방향을 보장하지 못합니다.
오답: ① 이진 탐색은 인덱스 접근이 O(1)인 배열 구조에 적합하며, 연결 리스트는 오히려 부적합합니다.
정답: ② 정렬된 상태가 이진 탐색의 핵심 전제 조건입니다.
오답: ③ 원소 개수의 홀짝 여부는 이진 탐색 동작에 영향을 주지 않습니다.
오답: ④ 중복 값이 있어도 이진 탐색은 동작 가능하며, 중복 제거는 전제 조건이 아닙니다.
문제 2. 이진 탐색의 시간 복잡도
크기가 n인 정렬된 배열에서 이진 탐색(Binary Search)을 수행할 때의 평균 및 최악 시간 복잡도로 올바른 것은?
- 평균 O(n), 최악 O(n²)
- 평균 O(log n), 최악 O(n)
- 평균 O(log n), 최악 O(log n)
- 평균 O(1), 최악 O(log n)
정답
③ 평균 O(log n), 최악 O(log n)
해설
이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄이므로, 최대 비교 횟수는 log₂n에 비례합니다. 따라서 평균과 최악 모두 O(log n)입니다. 데이터 분포에 상관없이 항상 절반씩 범위를 좁히기 때문에 평균과 최악이 동일합니다.
오답: ① O(n)과 O(n²)은 각각 선형 탐색과 버블 정렬 등의 복잡도로, 이진 탐색과 무관합니다.
오답: ② 최악이 O(n)이 되는 경우는 선형 탐색(순차 탐색)에 해당합니다.
정답: ③ 이진 탐색은 평균과 최악 모두 O(log n)으로 동일합니다.
오답: ④ O(1)은 해시 탐색의 평균 복잡도이며, 이진 탐색의 평균과 다릅니다.
문제 3. 해시 탐색의 특징
해시 탐색(Hash Search)에 대한 설명으로 가장 옳지 않은 것은? 정보처리기사 알고리즘 복잡도 문제에서 자주 출제되는 개념입니다.
- 해시 함수를 이용해 키 값을 배열 인덱스로 변환하여 탐색한다.
- 충돌(Collision)이 발생하지 않을 경우 평균 탐색 시간은 O(1)이다.
- 데이터가 정렬된 상태일 때만 사용할 수 있다.
- 충돌 해결 방법으로 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있다.
정답
③ 데이터가 정렬된 상태일 때만 사용할 수 있다. — 이것이 틀린 설명입니다.
해설
해시 탐색은 해시 함수로 키를 인덱스에 직접 매핑하므로, 데이터의 정렬 여부와 무관하게 동작합니다. 정렬이 전제 조건인 탐색 방법은 이진 탐색입니다. 따라서 ③은 해시 탐색의 특징을 잘못 설명한 옳지 않은 보기입니다.
오답: ① 해시 탐색의 기본 원리를 올바르게 설명한 맞는 설명입니다.
오답: ② 충돌이 없을 때 O(1)이 되는 것은 해시 탐색의 대표적인 장점으로 올바릅니다.
정답(오답 보기): ③ 해시 탐색은 정렬 여부와 무관하므로 이 설명은 틀립니다.
오답: ④ 체이닝과 개방 주소법은 대표적인 충돌 해결 방법으로 올바른 설명입니다.
문제 4. 공간 복잡도의 개념
알고리즘의 공간 복잡도(Space Complexity)에 대한 설명으로 옳지 않은 것은?
- 공간 복잡도는 알고리즘 실행에 필요한 메모리 공간의 양을 분석한다.
- 입력 크기 n에 무관하게 추가 메모리를 일정하게 사용하면 공간 복잡도는 O(1)이다.
- 재귀 알고리즘은 호출 스택 공간을 사용하므로 공간 복잡도에 영향을 준다.
- 시간 복잡도가 낮은 알고리즘은 항상 공간 복잡도도 낮다.
정답
④ 시간 복잡도가 낮은 알고리즘은 항상 공간 복잡도도 낮다. — 이것이 틀린 설명입니다.
해설
시간 복잡도와 공간 복잡도는 서로 독립적인 개념입니다. 시간 복잡도를 줄이기 위해 추가 메모리를 더 사용하는 경우도 많습니다. 예를 들어, 동적 프로그래밍은 반복 연산을 줄이는 대신 결과를 저장하는 메모리를 추가로 요구합니다. 이는 시간·공간 간의 트레이드오프(Trade-off)를 보여주는 대표적인 사례입니다.
오답: ① 공간 복잡도의 정의를 올바르게 설명한 맞는 설명입니다.
오답: ② 추가 메모리가 입력 크기와 무관하면 O(1)로 표기하며 올바른 설명입니다.
오답: ③ 재귀 호출 시 스택 프레임이 쌓이므로 공간 복잡도에 영향을 주는 것은 올바릅니다.
정답(오답 보기): ④ 시간과 공간 복잡도는 독립적이며, 시간이 낮다고 공간도 낮다는 보장이 없습니다.
문제 5. 분기 한정법과 백트래킹의 비교
최적화 문제를 탐색으로 해결하는 두 가지 기법인 백트래킹(Backtracking)과 분기 한정법(Branch and Bound)에 대한 설명으로 옳은 것은?
- 백트래킹은 한계 비용(Bound)을 계산하여 최적해가 될 수 없는 경로를 가지치기한다.
- 분기 한정법은 목표 상태에 도달할 수 없는 경로를 탐색 중 포기하고 되돌아간다.
- 분기 한정법은 최솟값 또는 최댓값을 구하는 최적화 문제에 주로 사용된다.
- 백트래킹과 분기 한정법은 최악의 경우 모든 경우를 탐색하지 않는 것을 보장한다.
정답
③ 분기 한정법은 최솟값 또는 최댓값을 구하는 최적화 문제에 주로 사용된다.
해설
분기 한정법(Branch and Bound)은 각 분기마다 한계 비용(Bound)을 계산하여 현재보다 나은 해가 나올 수 없는 경우를 가지치기합니다. 이를 통해 최적화 문제(최솟값·최댓값 탐색)를 효율적으로 풀 수 있습니다. 한편, 백트래킹은 가능·불가능 여부를 판단해 유망하지 않은 경로를 포기하는 방식으로, 최적화보다는 해의 존재 여부 판별에 더 자주 사용됩니다.
오답: ① 한계 비용(Bound)을 계산하여 가지치기하는 것은 백트래킹이 아니라 분기 한정법의 특징입니다.
오답: ② 목표 상태에 도달 불가 시 되돌아가는(백트랙) 것은 분기 한정법이 아니라 백트래킹의 특징입니다.
정답: ③ 분기 한정법은 최적화 문제(최솟값·최댓값 탐색)에 주로 사용되는 올바른 설명입니다.
오답: ④ 두 기법 모두 최악의 경우 모든 경우를 탐색할 수 있으므로, 탐색 생략을 ‘보장’한다는 설명은 틀립니다.
학습 정리
이번 회차에서는 이진 탐색의 전제 조건과 O(log n) 복잡도, 해시 탐색의 O(1) 평균 성능과 충돌 해결 방법을 핵심으로 다뤘습니다. 또한 공간 복잡도는 시간 복잡도와 독립적임을 기억하고, 분기 한정법과 백트래킹의 차이를 명확히 구분해야 합니다. 정보처리기사 알고리즘 복잡도 문제는 이처럼 개념 간 차이를 묻는 형태로 자주 출제되므로, 각 알고리즘의 조건·복잡도·활용 목적을 함께 정리하는 것이 효과적입니다.