방통대 방송대 알고리즘 출석수업과제물 A+

소개

"방통대 방송대 알고리즘 출석수업과제물 A+"에 대한 내용입니다.
방통대에 제출한 과제(중간과제물, 기말과제물, 출석수업 과제물)는 모든 과목에서 전부 만점을 받았습니다.

목차

1.다음은 입력 크기 n에 대한 빅오 함수들이다. 알고리즘의 성능 관점에서 가장 나쁜 것부터 차례대로 나열하시오.
2.다음 4가지 경우에 해당하는 점화식과 폐쐐형을 쓰시오.
3.대표적인 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.
4.주어진 배열에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후의 결과 배열을 구하시오. (단, A[0]이 피벗이다.)
5.물체를 쪼갤 수 있는 배낭 문제에 대해서 욕심쟁이 방법을 적용해서 최대 이익을 구하시오.
6.다음 그래프에 대한 최소 신장 트리와 해당 트리의 가중치의 합을 구하시오.

본문내용

1. 알고리즘 성능 관점에서 나쁜 순으로 나열
▶ O(2n) → O(n3) → O(n2) → O(nlogn) → O(n) → O(logn) → O(1)
2. 점화식과 폐쇄형
① 이진 탐색
T(n) = Θ(1), n=1
= T(n/2) + Θ(1), n>=2
▶ T(n) = Θ(logn)
② 퀵 정렬 최악의 경우
T(n) = Θ(1), n=1
= T(n-1) + Θ(n), n>=2
▶ T(n) = Θ(n2)
③ 합병 정렬
T(n) = Θ(1), n=1
= 2T(n/2) + Θ(n), n>=2
▶ T(n) = Θ(nlogn)
④ 퀵 정렬 최선의 경우
T(n) = Θ(1), n=1
= 2T(n/2) + Θ(n), n>=2
▶ T(n) = Θ(nlogn)

3. 알고리즘 설계 기법이 적용된 문제들의 정의/개념
① 분할정복 알고리즘
 이진 탐색: 데이터가 정렬된 상태로 주어진 원소들을 절반씩 나누면서 원하는 키값을 찾는 방식이다. 이진 탐색은 데이터가 정렬된 리스트라고 가정을 하고, 탐색키와 정렬된 배열 가운데 위치한 원소와 비교하여 두 값이 같을 때까지 탐색한다.
 합병 정렬: 분할정복 방법에 해당한다. 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각 부분배열을 합병 정렬한 다음, 정렬된 두 부분배열을 결합하여 한 개의 정렬된 배열을 만드는 방식이다.
 퀵 정렬: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할한 후, 각 부분배열에 대해 순환적으로 퀵 정렬을 적용하면서 피벗이 제자리를 잡도록 정렬하는 방식이다. 합병 정렬은 동일한 크기로 두 부분배열로 분할/결합하지만, 퀵 정렬은 분할된 두 부분배열 크기가 일정하지 않고 합병 단계가 필요하지 않다는 차이점이 있다.

참고자료

· 없음