목록분할과정복 (1)
minkylee
[분할과 정복] 개념 정리
분할 정복이란? 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합 정렬이 있다. 그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다. 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다. 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. 마스터 정리 점화식을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복 알고리즘에서 주로 사용된다. 점화식이 특정한 ..
CSE/컴퓨터알고리즘
2024. 4. 20. 19:16