알고리즘(분할정복법, 동적계획법, 탐욕법) 레포트

1. 분할정복법(Divide and Conquer)

분할정복법은 문제를 해결하는 고전적인 알고리즘 설계 기법 중 하나이다. 이 방식은 복잡한 문제를 더 작은 하위 문제로 나눈 뒤, 각 하위 문제를 독립적으로 해결하고, 이들을 결합하여 원래 문제의 해를 구하는 방식이다. 분할정복법의 핵심은 문제를 효과적으로 나누어 해결할 수 있는 구조를 갖추고 있다는 점이다. 분할정복법의 기본 단계는 세 가지로 요약될 수 있다. 우선 주어진 문제를 여러 개의 하위 문제로 나눈다. 이때 나눈 하위 문제들은 원래 문제와 유사한 성격을 가지며, 문제의 크기가 작아진다. 그 다음으로 하위 문제를 재귀적으로 해결한다. 이 단계에서 각 하위 문제는 분할정복법을 통해 다시 나누어지고 반복적으로 해결된다. 마지막으로 각 하위 문제의 해를 결합하여 원래 문제의 해를 구성한다. 이러한 과정은 문제이 주어진 형태와 조건에 따라 여러 번 반복될 수 있으며, 이로 인해 알고리즘의 복잡도와 효율성이 결정된다. 분할정복법의 대표적인 예는 합병 정렬(merge sort)이다. 합병 정렬은 배열이나 리스트를 정렬하는 알고리즘으로, 배열을 중간에서 나누어 두 개의 하위 배열로 분할한다. 그런 다…