방통대 (방송통신대학교) 컴퓨터과학과 알고리즘 중간과제물

소개

방통대 (방송통신대학교) 컴퓨터과학과 알고리즘 중간과제물 입니다.

1. 다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하려고 한다. 이때 얻을 수 있는 최대 이익은 얼마인가? (단, 물체를 쪼갤 수 있다.)
2. 알고리즘의 성능을 나타내는 빅오 함수 중에서 가장 효율적인 것은?
3. 주어진 점화식의 폐쇄형과 이를 구하는 과정을 서술하시오.
4. 버블 정렬, 선택 정렬 그리고 삽입 정렬의 이론적 배경과 실제 성능을 비교 분석하시오. 이 알고리즘들의 시간 복잡도를 이해하고, 각각의 정렬 방식이 다른 데이터 상황에서 어떻게 작동하는지 비교하시오.

목차

없음

본문내용

1. 다음과 같은 조건의 배낭 문제를 욕심쟁이 방법으로 해결하려고 한다. 이때 얻을 수 있는 최대 이익은 얼마인가? (단, 물체를 쪼갤 수 있다.) (2점)
M = 10, n = 4
(p_1, p_2,p_3,p_4) = (18, 20, 9, 20)
(w_1, w_2,w_3,w_4) = (3, 5, 3, 4)

① 47 ② 49 ③ 50 ④ 58

답: ③ 50
풀이: 먼저, 물체를 쪼갤 수 있음으로 단위 무게당 이익을 구하면 (18/3, 20/5, 9/3, 20/4) = (6, 4, 3, 5)이다.
단위 무게가 높은 순으로 물체를 넣으면 물체1 → 물체4 → 물체2 → 물체3의 순서대로 넣을 수 있다. 배낭의 무게가 10임으로 배낭에는 물체1, 물체4, 물체2의 3/5만큼을 넣을 수 있다. 따라서 최대 이익은 물체 1의 이익 + 물체 4의 이익 + 물체2의 이익의 3/5 임으로 18 + 20 + 12 = 50이다.

2. 알고리즘의 성능을 나타내는 빅오 함수 중에서 가장 효율적인 것은? (2점)
① O(nlogn) ② O(logn) ③ O(n2) ④ O(2n)

답: ② O(logn)
풀이: 빅오 함수 간의 크기 관계를 나타내면 O(1) < O(logn) < O(n) < O(nlogn)< O(n2)< O(n3)< O(2n)으로 나타낼 수 있다. O(1)은 입력 크기에 관계없이 수행시간이 일정한 상수 시간이며, 뒤로 갈수록 입력 크기에 따라 수행시간이 커지는 빅오 함수이다. 따라서 보기 중에서 가장 효율적인 함수는 ② O(logn)이다.

3. 주어진 점화식의 폐쇄형과 이를 구하는 과정을 서술하시오. (9점, 1개당 3점)

참고자료

· 없음