[컴퓨터과학과] 2020년 1학기 알고리즘 출석수업대체시험 과제물(분할정복 방법, 동적 프로그래밍 방법)

목차

① 알고리즘의 대표적인 설계기법인 분할정복 방법(2장), 동적 프로그래밍 방법(3장), 욕심쟁이 방법(4장)의 원리 및 특징을 비교 설명하고,
② 각 방법들이 적용된 알고리즘(또는 문제)의 종류와 각각의 특징/성능을 간단히 정리하시오.


- 목 차 -

I. 서 론

II. 본 론
1. 알고리즘의 설계기법
1) 분할정복 방법
2) 동적 프로그래밍 방법
3) 욕심쟁이 방법

2. 각 방법들이 적용된 알고리즘(또는 문제)
1) 합병 정렬 - 분할정복 방법
2) 플로이드(Floyd) 알고리즘 - 동적 프로그래밍 방법
3) 크루스칼(Kruskal)의 알고리즘 - 욕심쟁이 방법

III. 결 론

참고문헌


<< 함께 제공되는 참고자료 한글파일 >>
1. 동적 프로그래밍 방법.hwp
2. 분할정복법.hwp
3. 욕심쟁이 방법.hwp
4. 크루스칼 알고리즘이란.hwp
5. 플로이드 알고리즘(Floyd Algorithm).hwp
6. 합병 정렬(merge sort) 알고리즘의 개념.hwp

본문내용

I. 서 론

알고리즘은 일상 언어로 표시할 수도 있으나 일상 언어의 모호성 때문에 작업 과정을 정확히 기술하기 어려운 경우가 많고, 또한 일상 언어로 표현된 절차를 컴퓨터로 구현할 수 없는 경우가 많다. 따라서 이 책에서는 알고리즘이 지나치게 복잡한 경우를 제외하고는 가능한 한 C언어와 유사한 언어로 기술하기로 하며, 알고리즘이 지나치게 복잡하거나 또는 이해하기 어려운 경우에는 프로그래밍 언어와 비슷한 일상 언어로 기술하기로 한다.
알고리즘의 설계 과정은 쉽게 설명하기 어려운 창조적 활동이다. 예를 들어 여러 개의 숫자를 주고 그 중에서 제일 큰 숫자를 찾는 문제가 있다 하자. 아마 대부분의 사람은 쉽게 처음 두 숫자를 비교하여 큰 것을 찾아내고, 이어 그 숫자와 나머지 숫자 중 하나를 비교하여 위의 작업을 반복하면 될 것이라고 생각할 것이다. 즉, 이 경우는 비교적 쉽게 알고리즘을 구상할 수 있다. 반면 숫자를 여러 개 주고 이들 숫자 중 임의로 몇 개의 숫자를 선택하여 그들의 합이 특정 값이 되게 하라는 문제가 주어질 경우 단번에 알고리즘을 찾아내기는 쉽지가 않다. 특히 이 문제는 아직 소요시간이 비교적 작은 효율적인 알고리즘을 찾지 못한 대표적인 문제 중 하나이다.
알고리즘을 설계할 때 직선적인 방법은 주어진 문제를 컴퓨터를 사용하지 않고 해결하는 과정을 우선 생각한 후 이를 컴퓨터로 구현하는 방법이다. 이 방법은 많은 경우 합리적인 해결 방안을 낳는다. 예를 들면 주어진 여러 숫자 중 제일 큰 수를 찾거나, 또는 주어진 숫자들을 크기순으로 정렬하는 문제는 통상 우리가 하는 방법대로 숫자들을 적절한 순서로 비교하여 원하는 결과를 도출하는 알고리즘을 얻을 수 있다. 순차적으로 주어진 숫자들을 비교하는 방법은 우리가 직감적으로 수행하는 방법과 동일하며, 단지 그 방법을 컴퓨터로 수행하는 것에 불과하다. 그러나 조금만 더 생각해 보면 숫자들을 비교하는 순서를 여러 방법으로 바꿀 수 있음을 알 수 있다.
이 레포트는 알고리즘의 대표적인 설계기법의 원리 및 특징에 대해 서술하였다.


II. 본 론

1. 알고리즘의 설계기법

1) 분할정복 방법
분할정복 방법은 순환적으로 문제를 푸는 방법으로서 주어진 문제를 여러 개의 소문제로 분할하여 이 소문제를 순환적으로 푼 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식이다. 즉, 순환 호출시마다 다음과 같은 세 단계의 작업이 이루어진다.





- 중략 -

참고 자료

없음