알고리즘 ) 알고리즘의 대표적인 설계기법인 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법의 원리 및 특징을 비교 설명

목차

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

본문내용

알고리즘(Algorithm)은 수학과 주어진 문제를 해결하기 위한 일련의 절차 또는 방법을 공식화하여 표현한 것으로 문제 해결에 필요한 계산을 실행하기 위한 단계적 절차를 의미한다. 알고리즘이 문제 해결의 효율을 결정짓는다고 하여도 과언이 아니다. 기본적으로 작성되어있는 알고리즘의 설계기법들을 응용하여 보다 효과적으로 프로그램을 개발하는 것이 가능하기 때문에 알고리즘 설계기법에 대해 정리해둘 필요가 있다. 대표적인 알고리즘 설계기법 중 대표적인 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법의 원리 및 특징을 비교 설명하도록 한다.
- 분할정복 방법(divide-and-conquer)
복잡하고 큰 문제를 분할하여 작은 문제로 만들어서 복잡도와 규모를 감소시켜 해결하는 알고리즘 설계기법이다. 해결하고자하는 문제의 크기가 n이라고 가정할 때 이를 크기가 n보다 작은 문제들로 분할하여 점차적으로 해결해나가게 된다. 분할정복 방법은 일반적으로 이를 사용하지 않은 알고리즘보다 효율성면에서 뛰어나다.

참고 자료

없음