[방송통신대학교] 알고리즘 출석수업대체과제물

소개글

"[방송통신대학교] 알고리즘 출석수업대체과제물"에 대한 내용입니다.

알고리즘 출석수업대체과제물은 특징을 비교하고 성능을 정리하는 내용을 담고있는 과제입니다.
책에서 나온 내용을 잘 요약하여 비교하는 글이며, 특징과 성능을 잘 정리하여 쓴 내용입니다.
해당 과제로 A+의 성적을 받았습니다.
잘 활용하여 좋은 점수 받으시길 바랍니다.

목차

1. 분할정복방법, 동적프로그래밍방법, 욕심쟁이 방법의 원리 및 특징 비교

2. 각 방법이 적용된 알고리즘의 종류와 특징/성능 정리
1) 분할정복 방법
2) 동적프로그래밍방법
3) 욕심쟁이 알고리즘

본문내용

분할정복방법, 동적프로그래밍방법, 욕심쟁이방법 이 세 가지 방법의 원리에는 차이가 있다. 먼저, 분할정복방법의 원리는 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 ‘하향식 접근 방법’이다. 반면 동적프로그래밍방법은 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 ‘상향식 접근 방법’이라고 할 수 있다. 마지막으로 욕심쟁이 방법의 원리는 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 ‘전체적인 최적해를 구하는 방법’이다.
각각의 방법에는 특징이 있는데, 분할정복방법의 특징으로 분할된 작은 문제들이 서로 독립적이라는 것을 들 수 있다. 따라서 한 번 사용한 소문제의 해는 더 이상 필요하지 않다. 반면 동적프로그래밍방법은 소문제들이 서로 독립적이지 않고 중복되는 부분이 존재한다.

참고 자료

없음