[알고리즘] 분할정복(Divide and Conquer)

1. 분할정복(Divide and Conquer)이란 

• 여러 알고리즘의 기본이 되는 해결방법
• 엄청나게 큰 문제를 풀 수 있는 단위로 나눠서 각각을 해결한 후 다시 합병해서 문제의 답을 얻는 알고리즘을 말하는데
• 특정한 문제를 풀기위한 알고리즘이 아니라 문제 풀이 전략이다.
• 대표적으로 퀵정렬과 병합 정렬이 있다.

 

• 분할(divide): 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
• 정복(conquer): 분할한 문제를 해결한다.
• 조합(combine): 정복한 문제들을 합쳐서(조합하여) 원래 문제의 답을 얻는다.

2. 퀵정렬과, 병합정렬 외의 다른 분할정복의 예

public class Factorial{
    public int factorialFunc(int data){
        if(data <= 1){
            return data;
        }
        return this.factorialFunc(data - 1) + this.factorialFunc(data - 2);
    }	
}