
[Algorithm/Divide&Conquer] 01. 분할 정복(Divide & Conquer) 알고리즘
·
Computer Science/Algorithm
분할 정복 설계 패러다임효율적인 알고리즘을 설계하기 위한 일반적인 접근 방법이 개발되어 다양한 문제 해결에 사용되고 있다.분할 정복(divide-and-conquer)은 가장 널리 사용되는 알고리즘 설계 패러다임 중 하나이다.분할 정복 알고리즘이란?주어진 문제를 작은 부분 문제로 나누고, 나줘진 각 부분 문제의 솔루션을 구하고, 각 부분 문제 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식binary search(이진 탐색), quick sort(퀵 정렬), merge sort(병합 정렬), matrix mulitplication(행렬 곱셈), Fast Fourier Trnasform(고속 푸리에 변환), skyline algorithm(스카이라인 알고리즘) 등에서 사용되는 패러다임이다.분할 정복..