방송통신대 알고리즘 출석수업 과제

1. 대표적인 3가지의 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.

알고리즘 설계 기법은 문제를 해결하기 위한 다양한 접근 방식을 제공한다. 여기에서는 대표적인 3가지 알고리즘 설계 기법인 분할 정복, 다이나믹 프로그래밍, 탐욕 알고리즘을 각각 설명한다. 분할 정복은 복잡한 문제를 더 단순한 여러 하위 문제로 나누어 해결하는 방법이다. 이 기법은 주어진 문제를 여러 개의 부분 문제로 재귀적으로 분할하고, 부분 문제들을 독립적으로 해결한 뒤, 이를 조합하여 원래 문제의 해결책을 얻는다. 예를 들어, 병합 정렬(Merge Sort)은 분할 정복 기법을 이용하여 정렬 문제를 해결한다. 배열을 반으로 나누고 각각을 정렬한 후, 정렬된 두 하위 배열을 합쳐 최종적으로 정렬된 배열을 만드는 방식이다. 이와 같이 분할 정복은 문제를 효율적으로 해결할 수 있는 강력한 방법이다. 다이나믹 프로그래밍은 최적화 문제를 해결하기 위해 사용되는 기법으로, 문제를 여러 개의 하위 문제로 나눈 후, 이 하위 문제들의 해답을 저장하여 중복 계산을 피하는 방식이다. 이 기법은 최적 부분 구조와 중복 부분 …