알고리즘 통계데이터과학과 방송통신대학교

목차

없음

본문내용

1. 퀵 정렬에서 분할 함수 Patition() 수행 시간의 시간 복잡도를 설명하시오. 주어진 데이터를 퀵 정렬 하시오. A[]={30, 35, 40, 45, 10, 25, 50}
① 분할함수 Partition()의 복잡도는 피벗으로 지정한 첫 번째 원소를 제외한 나머지 모든 원소를 피벗과 한 번 또는 두번의 비교를 수행하기 때문에 전체적으로는 입력크기 n에 비례하는 Θn 시간이 걸린다.
② A[]={30, 35, 40, 45, 10, 25, 50}의 퀵 정렬은 다음과 같다
(1) {30, 35, 40, 45, 10, 25, 50} 피벗 선정
(2) {30, 25, 40, 45, 10, 35, 50} 25와 35 자리 바꿈
(3) {30, 25, 10, 45, 40, 35, 50} 10과 40 자리 바꿈
(4) {10, 25, 30, 45, 40, 35, 50} 10과 30 자리 바꿈
(5) {10, 25, 30, 40, 35, 45, 50} 45자리 이동
(6) {10, 25, 30, 35, 40, 45, 50} 40자리 이동
(7) 정렬 결과 A[]={10, 25, 30, 35, 40, 45, 50}

2. 용량이 20인 배낭이 있다. 물체의 이익과 무게가 다음과 같이 주어져 있고 물체를 쪼개 넣을 수 있다고 할 때 배낭에 넣기 위한 진행 과정과 최대 이익을 구하시오. 반드시 풀이과정을 정확히 작성하시오. 다음 쌍에는 앞에는 물체의 무게, 뒤에는 이익이 주어져 있으며, 물체 1부터 순서대로 나열되어 있다. (7, 21), (5, 20), (4, 28), (6, 36), (2, 10)
① 각 물건의 이익을 무게로 나눈다.
물체1 : 21/7 = 3
물체2 : 20/5 = 4
물체3 : 28/4 = 7
물체4 : 36/6 = 6
물체5 : 10/2 = 5

참고자료

· 「알고리즘」, 한국방송통신대학교출판문화원, 2022