분할 정복(divide-and-conquer) 알고리즘에 대한 설명으로… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

1[7급 국가직 알고리즘] 23년 1회차

분할 정복(divide-and-conquer) 알고리즘에 대한 설명으로 옳은 것은?

이진 탐색(binary search)은 분할 정복 알고리즘에 속한다.

분할 정복에 기반을 둔 알고리즘의 시간 복잡도는 최악의 경우  $O(\log_2(n))$ 이다.

반복문(iteration)만을 사용하여 큰 문제를 작은 문제들로 분할한다.

 $n$ 개의 정수들 중  $k$ 번째로 큰 정수를 찾는 선택(selection) 문제에서 문제의 크기는 재귀적으로 절반씩 분할된다.

해설

이진 탐색은 탐색 구간을 절반으로 나눠 한쪽만 재귀적으로 푸는 분할 정복 알고리즘이다.

가운데 원소와 비교해 문제를 크기 절반의 부분 문제 하나로 줄이므로, 분할 정복의 가장 단순한 형태다.

분할 정복 알고리즘의 복잡도는 문제마다 다르다. 병합 정렬은 $O(n\log_2(n))$ , 퀵 정렬은 최악 $O(n^2)$ 이므로 일괄적으로 $O(\log_2(n))$ 라 할 수 없다.
분할 정복은 보통 재귀로 큰 문제를 작은 문제로 나누므로, 반복문만 사용한다는 설명은 틀리다.
선택 문제는 분할 원소(피봇)를 기준으로 나누므로 부분 문제 크기가 피봇 위치에 따라 달라지며, 항상 절반씩 분할되는 것은 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기