방통대 알고리즘 출석과제물

소개글

방통대 알고리즘 출석과제물 2023년도 1학기에 작성되었으며, 기출문제를 확인하면서 출석과제물을 어렵지 않게 확인할 수 있습니다. 본 출석과제물로 무난한 점수를 획득하였습니다.

목차

없음

본문내용

1. 다음은 입력 크기 n에 대한 빅오 함수들이다. 알고리즘의 성능 관점에서 가장 나쁜 것부터 차례대로 나열하시오.

2. 다음 4가지 경우에 해당하는 점화식과 폐쇄형을 쓰시오.
① 이진 탐색
② 퀵 정렬의 최악의 경우
③ 합병 정렬
④ 퀵 정렬의 최선의 경우
3.. 대표적인 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.
4. 주어진 배열에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후의 결과 배열을 구하시오. (단, A[0]이 피벗이다.)
A[] = { 35, 50, 25, 40, 70, 20, 45, 55, 30, 10 }
5. 물체를 쪼갤 수 있는 배낭 문제에 대해서 욕심쟁이 방법을 적용해서 최대 이익을 구하시오.
M = 10, n = 4
(p1, p2, p3, p4) = (15, 20, 16, 24), (w1, w2, w3, w4) = (4, 5, 3, 7)
6. 다음 그래프에 대한 최소 신장 트리와 해당 트리의 가중치의 합을 구하시오
ⓑ 7
8 1 ⓓ
ⓐ 5 ⓔ 6 2
3 4 3 ⓕ
ⓒ 5

1. 다음은 입력 크기 n에 대한 빅오 함수들이다. 알고리즘의 성능 관점에서 가장 나쁜 것부터 차례대로 나열하시오.

O(2ⁿ) -> O(n³) -> O(n²) -> O(nlogn) -> O(n) -> O(logn) -> O(1)

참고 자료

없음