방송통신대(방통대) 서울남부 컴퓨터과학과 알고리즘 출석수업과제물

소개

"방송통신대(방통대) 서울남부 컴퓨터과학과 알고리즘 출석수업과제물"에 대한 내용입니다.

목차

Ⅰ. [문제1] 출석수업에서 배운 대표적인 알고리즘 설계기법을 설명한 후 각각에 해당되는 알고리즘을 모두 설명하시오.
Ⅱ. [문제2] 용량이 20인 배낭이 있다. 물체의 이익과 무게가 다음과 같이 주어져 있고 물체를 쪼개 넣을 수 있다고 할 때 배낭에 넣기 위한 진행 과정과 최대 이익을 구하시오. 반드시 풀이과정을 정확히 작성하시오. 다음 쌍에는 앞에는 물체의 무게, 뒤에는 이익이 주어져 있으며, 물체 1부터 순서대로 나열되어 있음. (7, 21), (4, 16), (4, 28), (6, 36), (3, 15)
Ⅲ. [문제3] 주어진 원소를 이진탐색 하시오. (탐색키 = 20) A[] = {20, 25, 30, 35, 40, 45, 50}
Ⅳ. [문제4] 주어진 데이터를 퀵정렬 하시오. (단, Partition 함수가 1번 호출되었을 경우) 퀵정렬을 2가지 관점(①안정적인 정렬, ②제자리 정렬)에 대해서 모두 설명하시오.
Ⅴ. [문제 5] 셸(shell) 정렬과 합병 정렬을 설명(개념, 원리, 성능, 특징 포함)하시오. 셸 정렬에서 순열에 대하여 설명하시오. 합병 정렬에서 가장 핵심이 되는 주요 함수 한 가지를 설명하시오.

본문내용

[문제1]
출석수업에서 배운 대표적인 알고리즘 설계기법을 설명한 후 각각에 해당되는 알고리즘을 모두 설명하시오.
대표적인 알고리즘 설계기법으로는 욕심쟁이 방법과 분할정복 방법이 있다. 먼저, 욕심쟁이 방법은 해를 구하는 선택과정에서 전후 단계의 선택과는 무관하게 각 단계에서의 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다. 물론 각 단계마다 선택한 국부적인 최적해가 전체적인 최적해를 만든다는 보장은 없지만, 각 단계마다 최적해를 선택한다는 간단한 방법을 가지고 있어 간단하고 효율적인 알고리즘을 만들 수 있는 설계방식이다. 욕심쟁이 방법은 최댓값, 최솟값을 구하는 최적화 문제에서 많이 사용되고, 이를 적용하는 대표적인 문제로 거스름돈 문제, 배낭 문제 등이 있다.

참고자료

· 없음