Chap 3. 분할 정복 알고리즘

분할정복 알고리즘

: 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘

  부분 해(분할)를 취합( =정복)하여 원래 문제의 해를 얻음

• 부분문제와 부분해

더 이상 분할할 수 없을 때까지 분할한다. → 분할한 문제들의 해를 취합 → 부분 취합을 다시 취합

 

(1) 분할 과정

[상황]

입력 = n

분할 = n을 3개로 분할

각각 분할된 부분 문제의 크기 = n/2

*질문 = 여기서 n을 3개로 분할한 것이므로 각각 분할된 부분 크기는 n/3이 아닌가?
⇒ n이라는 전체 크기를 3등분하여 반으로 나눈다는 의미
    3등분을 전체에 대한 것이 아니라 전체의 반의 반이 하나의 등분으로 생각하면 된다.

 

[ 이를 일반화 하면 ] 

입력 = n

분할 = n을 b개로 분할

각각 분할된 부분 문제의 크기 = n/a

여기서 더 이상 "분할할 수 없을 때"까지 반복하여 분할한다.

입력 크기가 n일 때 총 분할 횟수

[ 질문 ] 몇번을 분할해야 더이상 분할할 수 없을 때까지 하는가?

입력 = n 개

분할해야할 횟수의 답(더 이상 분할될 수 없을 때까지 분할한 횟수) = k

총 분할한 횟수 = k라면

• 1번 분할 후 각 입력 크기 n/2

• 2번 분할 후 각 입력 크기 n/2^2

   ⋮

• k번 분할 후 각 입력 크기 n/2^k

• n/2^k = 1일 때 분할 못함

• k = log2n

(2) 정복 과정

• 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없으므로

      분할된 부분 문제들의 부분 해를 찾아야 한다. (정복해야 함)

• 정복하는 방법은 문제에 따라 다르다

 

 

분할 정복 알고리즘의 분류

(1) 분할 정복 알고리즘은 분할되는 부분 문제의 수와 부분 문제의 크기에 따라서 다음과 같이 분류

• 문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘

• a=b=2인 경우: 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제

• a=3, b=2인 경우: 큰 정수의 곱셈

• a=4, b=2인 경우: 큰 정수의 곱셈

• a=7, b=2인 경우: 스트라센(Strassen)의 행렬 곱셈 알고리즘

 

(2) 문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

     ex) 퀵 정렬

 

(3) 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 1/2로 감소하는 알고  리즘 (일정한 크기로 감소)

 -하나의 부분은 버려버리는 문제

  ex) 이진 탐색

 

 

(4) 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 선택 문제 알고리즘

   ex) 선택 문제 알고리즘

 

 

(5) 부분 문제의 크기가 1, 2개씩 감소하는 알고리즘

    ex) 삽입 정렬(1개씩 감소), 피보나치 수의 계산(2개의 값을 고려하여 자리 찾기 → 2개씩 감소)