[30점만점] 출석수업 과제물 알고리즘
- 최초 등록일
- 2021.04.21
- 최종 저작일
- 2021.04
- 11페이지/
어도비 PDF
- 가격 8,000원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
소개글
"[30점만점] 출석수업 과제물 알고리즘"에 대한 내용입니다.
목차
1. 다음은 입력 크기 n에 대한 빅오 함수들이다. 알고리즘의 성능 관점에서 가장 나쁜것부터 차례대로 나열하시오.
2. 다음 4가지 경우에 해당하는 점화식과 폐쇄형을 쓰시오. (이진탐색, 퀵 정렬의 최악의 경우, 합병 정렬, 퀵 정렬의 최선의 경우)
3. 대표적인 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고 해당 문제의 정의하고 개념에 대해서 간단히 설명하시오.
4. 주어진 배열에 대해서 퀵 정렬의 분할함수 Partition()을 한번 적용한 후의 결과 배열을 구하시오 (단, A[0]이 피벗이다.)
5. 물체를 쪼갤 수 있는 배낭 문제에 대해서 욕심쟁이 방법을 적용해서 최대 이익을 구하시오
본문내용
빅오(Big-O) 함수는 알고리즘의 성능을 점근적으로 나타내는 표기법이다. 빅오 함수는 입력의 크기 n이 무한대로 커질 때 결정되는 성능의 최악의 경우 즉, 알고리즘의 성능이 아무리 나빠도 최악의 수행시간보다 작거나 같음을 의미한다. 주어진 입력 크기 n에 대한 빅오 함수들을 성능이 나쁜 함수부터 나열하면 다음과 같다.
2. 다음 4가지 경우에 해당하는 점화식과 폐쇄형을 쓰시오. (이진탐색, 퀵 정렬의 최악의
경우, 합병 정렬, 퀵 정렬의 최선의 경우)
주어진 문제를 동일한 형태의 작은 문제로 쪼개어 접근하는 분할정복의 형태를 띄는 알고리즘은 수행 과정에서 알고리즘을 다시 수행하는 형태를 취하고 있는데, 이를 순환 알고리즘이라 한다. 순환 알고리즘에서 수행시간을 나타내기 위해서는 사용되는 표기형태를 점화식(또는 재귀식)이라고 하며, 이를 기반으로 입력의 크기 n에 대해서 닫힌 형태의 식(closed-form expression), 즉 폐쇄형의 복잡도로 표기될 수 있다.
주어진 4가지 경우에 대해서 점화식과 폐쇄형은 아래와 같다
참고 자료
이관용, 김진욱. [알고리즘] 한국방송통신대학교출판문화원, 2018.