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

목차

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

본문내용

알고리즘의 대표적인 설계기법인 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법의 원리 및 특징을 비교 설명하기 이전에 그 원 개념인 알고리즘에 대해서부터 살펴보도록 한다. 우선, 알고리즘(Algorithm)이란, 해결해야한 문제를 처리하기 위한 여러 동작 또는 방법을 모아서 공식화하여 표현한 것이다. 문제를 해결하는데 있어 요구되는 계산 실행을 위한 단계적 절차이며 연산, 데이터 진행, 자동화된 추론 등을 처리한다. 효율적인 알고리즘이 문제 해결의 성능을 결정짓게 된다. 작성되어있는 알고리즘 설계기법들을 활용하게 되면 보다 효율적으로 프로그램을 개발하는 것이 가능하다. 그렇기 때문에 기본적인 알고리즘 설계기법에 대해 정리할 필요가 있다. 문제에서 요구하는 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법은 대표적인 알고리즘 설계기법 중 대표적인 기법이다. 해당 기법들의 원리 및 특징을 비교 설명하면 다음과 같다.

(1) 분할정복 방법(divide-and-conquer)
앞서 정리한 내용과 같이 분할정복 방법의 기본 원리는 크고 복잡한 문제를 작은 크기로 분할하여 해결해야할 문제의 복잡도와 규모를 줄여서 해결하는 알고리즘 설계기법이다. 해결해야할 문제의 크기가 n이라고 가정하고 주어진 문제를 그보다 작은 크기의 문제들로 크기를 분할하여 작은 크기의 간단한 문제부터 점진적으로 해결해나는 것이다. 일반적으로 분할정복 방법은 분할정복 방법을 활용하지 않은 알고리즘보다 뛰어난 효율성을 보인다. 대표적인 분할정복 방법으로는 퀵소트(Quick sort), 병합정렬(merge sort), 이분 탐색(binary search), 거듭제곱 연산(a^b) 등을 들 수 있다.
분할정복 방법의 장점과 단점에 대해서 살펴보면, 문제를 작게 분할하여 해결해나가기 때문에 주어진 문제가 어렵고 복잡하더라도 보다 쉽게 해결할 수 있다는 장점이 있다. 또한 이렇게 문제를 작게 분할하여 처리가 이루어진다는 특징상 병렬적 문제해결이 이루어진다는 것 또한 장점이다.

참고 자료

없음