방송통신대 알고리즘 출석수업 과제

소개글

2022년도 1학기 알고리즘 출석수업 과제

목차

1. 대표적인 3가지의 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.

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

3. 다음 4가지 경우에 해당하는 점화식과 폐쇄형을 쓰시오
1) 이진탐색
2) 퀵정렬의 최악의 경우
3) 합병정렬
4) 퀵정렬의 최선의 경우

4. 주어진 배열에 대해서 퀵 정렬의 분할 함수 Partition()을 한 번 적용한 후의 결과 배열을 구하시오. (단, A[0]이 피벗이다.)

5. 주어진 데이터에 대해서 합병 정렬의 전체적인 수행 과정을 나타내시오.

6. 주어진 데이터에 대해서 다음 조건에 따라 힙 정렬 과정의 결과를 표현하시오.

본문내용

1. 대표적인 3가지의 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.

⇒ 대표적인 알고리즘 설계 기법은 분할정복 방법, 동적프로그래밍 방법, 욕심쟁이 방법이 있다.
분할정복방법이 적용된 문제는 이진탐색, 합병 정렬, 퀵 정렬, 선택 문제가 있다.
이진탐색은 순서대로 정렬된 상태의 입력 데이터에 효과적인 탐색 방법이다. 오름차순으로 정렬되었다고 가정하고, 배열의 가운데 원소와 찾아야 하는 값 x를 비교하여 만일 원소가 x보다 작다면 가운데 원소 기준 오른쪽의 부분 배열에서 다시 가운데 원소를 찾는 순환호출을 진행하고, 원소가 x보다 클 경우 왼쪽의 부분 배열에서 순환호출을 진행한다. x와 가운데 원소가 같을 경우 가운데 원소의 인덱스를 반환하고 종료한다.
합병 정렬은 전형적인 분할정복 방법이 적용된 알고리즘으로, 주어진 배열을 더 이상 나눌 수 없을 때까지 순환하며 동일한 크기의 배열로 분할하고, 분할된 각 배열을 순환적으로 정렬한 후 정렬된 부분 배열 두 개를 순환적으로 결합하며 정렬된 배열을 만드는 방법이다. 결합 시 원소를 비교하며 작은 것부터 큰 순서로 정렬되도록 합병 함수를 사용한다.

참고 자료

없음