[방송통신대학교]알고리즘_출석수업과제(30점_만점)

소개글

[방송통신대학교]알고리즘_출석수업과제(30점_만점)

목차

1. 분할정복 방법에 대해 설명하시오.
2. 욕심쟁이 방법에 대해 설명하고 배낭문제의 사례로 정리하시오.
3. 삽입정렬, 퀵정렬, 합병정렬, 히프정렬에 대해 정리하고, 퀵정렬, 힙정렬에 대한 문제를 만들고 풀이과정을 설명하시오.
4. 순차탐색과 이진탐색에 대해 설명하고 이진탐색에 대한 문제를 만들고 풀이과정을 설명하시오.

본문내용

1. 분할정복 방법에 대해 설명하시오.
(1) 개념 : 순환적으로 문제를 푸는 하향식(top-down) 접근 방법으로, 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지, 두 개 이상의 작은 문제들로 계속해서 분할하고, 이렇게 반복하여 분할된 작은 문제들을 각각 해결한 뒤, 그 해들을 결합해서 원래 문제의 해를 구하는 방식을 분할정복이라고 한다.

(2) 특징 : 분할된 작은 문제들은 원래의 문제와 동일하다. 단지 입력의 크기만 작아졌을 뿐이다. 그리고 분할된 작은 문제들은 서로 독립적이기 때문에 순환적으로 분할을 할 수 있는 것이고, 그런 다음 그 결과들을 다시 통합하는 것이 가능한 것이다.

(3) 분할정복 방법의 처리 단계 : 각 순환 호출마다 세 단계의 처리 과정을 거친다.
① 분할 : 주어진 문제를 여러 개의 작은 문제들로 나눈다.
② 정복 : 더 이상 분할되지 않을 정도로 충분히 작은 크기로 문제가 분할이 됐다면, 더 이상 순환 호출 하지 않고 그 작은 문제들의 해를 구한다.
③ 결합 : 작은 문제에 대해 얻어진 해들을 결합, 통합하여 원래 문제의 해를 구한다. 주어지는 문제에 따라서 결합 단계가 필요 없는 경우도 존재한다.

(4) 분할정복 방법이 적용된 알고리즘
① 이진탐색 : 입력 데이터가 정렬된 상태로 주어졌을 때, 입력 크기를 절반씩 줄여가면서 원하는 데이터를 찾는 방법
② 퀵정렬 : 피벗을 기준으로 주어진 배열을 두 부분 배열로 분할하고, 각 부분 배열에 대해서 퀵 정렬을 순환적으로 적용하는 정렬 방식
③ 합병정렬 : 주어진 배열을 동일한 크기의 두 개의 부분 배열로 분할하고, 각각의 부분 배열을 순환적으로 정렬한 후, 정렬된 두 부분 배열을 합병하여 하나의 정렬된 배열을 만드는 정렬 방식
④ 선택문제 : n개의 원소가 임의의 순서로 저장된 배열에서 i번째로 작은 원소를 찾는 문제

2. 욕심쟁이 방법에 대해 설명하고 배낭문제의 사례로 정리하시오.
(1) 원리 : 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계의 처리 과정에서 가장 최선이라고 ......<중 략>

참고 자료

없음