[ 알고리즘 개념 ] 분할정복 (Divide and Conquer)
분할정복 분할정복은 방대해서 있는 그대로 해결할 수 없는 거대한 문제를 잘게 나누어서 각각의 작은 문제를 해결한 후 이 결과를 다시 합병하여 최종 결과를 내는 방법이다. 합병정렬이나 퀵 정렬 등 정렬문제에서도 사용되고, 슈트라센 알고리즘(Strassen Algorithm) 이나 고속 푸리에 변환(FFT) 문제 등 다방면의 문제 해결에서 사용된다. 분할정복을 설계할 때는 공통적으로 세 가지 과정을 거친다. (1) Divide (분할) - 문제를 잘게 쪼개기 ★(중요) (2) Conquer (정복) - 소문제를 해결하기 (3) Combine (병합) - 각각의 결과를 병합하여 최종 결과 도출하기 www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 ..
