알기쉬운알고리즘[개정판](생능출판,양성봉)-챕터3연습문제

소개

"알기쉬운알고리즘[개정판](생능출판,양성봉)-챕터3연습문제"에 대한 내용입니다.

목차

없음

본문내용

1. . 다음의 괄호 안에 알맞은 단어를 채워 넣어라
(1) ( 분할 정복 알고리즘이란 주어진 문제의 입력을 분할한 부분문제 )들을 해결하여 그
해를 취합하는 방식의 알고리즘이다.
(2) 분할 정복이 부적절한 경우는 입력이 분할될 때마다 부분문제들의 크기의 합이
분할되기 전의 크기보다 ( 커지는 ) . 경우이다
(3) 2 ( 합병 정렬에서 개의 정렬된 부분을 정렬 ) ( 하는 것은 분할 정복 알고리즘의 정복
) . 하는 과정이다
(4) ( 퀵 정렬에서는 피봇으로 분할 ) , ( 하여 부분문제가 만들어지며 별도의 병합 )과정이
없다.
(5) ( 선택 문제를 해결하는 분할 정복 알고리즘은 퀵정렬 ) 알고리즘과 같이 피봇을
사용하여 ( 부분문제 ) , ( 를 만들며 이진탐색과 같이 별도의 정렬 ) . 과정이 필요 없다
(6) ( ) , , 최근접 점의 쌍 문제를 해결하는 분할 정복 알고리즘의 정복 과정은 좌측 중간
우측 부분에서 최근접 점의 쌍을 찾는 것이다 ( ) .
2. ? n . 다음 중 합병 정렬에 대해 맞는 것은 단 입력 크기는 이다
① 입력과 같은 크기의 보조 배열 없이 구현할 수 없다.
② 입력과 같은 크기의 보조 배열 없이 구현하려면 시간이 소요된다 O(n) .
③ 입력과 같은 크기의 보조 배열 없이 시간에 구현할 수 있다 O(nlogn) .
④ 항상 크기의 배열 개가 필요하다 n/2 2 .
⑤ 답없음
3. ? 다음 중 퀵 정렬을 맞게 서술한 것은
① 입력을 비슷한 크기의 두 부분으로 합병하여 정렬한다.
② 입력을 크기가 서로 다를 수 있는 두 부분으로 나누어 보조 배열 없이 정렬한다.
③ 중앙값을 찾아 피봇으로 삼아 두 부분으로 나누어 정렬한다.
④ 이웃한 원소끼리 비교하여 비교 결과에 따라 자리바꿈을 수행하여 정렬한다.
⑤ 답 없음
4. ? 다음 중 퀵 정렬을 맞게 서술한 것은
① 평균 시간복잡도는 이고 최선 경우도 이다 O(nlogn) , O(nlogn) .
② 평균과 최악 경우의 시간복잡도는 이다 O(nlogn) .
③ 평균과 최악 경우의 시간복잡도는 이다 O(n^2) .
④ 최선 경우의 시간복잡도는 이고 최악 경우는 이다 O(n) , O(nlogn) .
⑤ 답 없음

참고자료

· 없음