DivideAndConquer ¶
어떤 N이라는 입력데이터를 가지는 문제에 대해서, 데이터를 일정한 상수 개수로 나눠서(divide), 각각의 나눠진 데이터에 대해서 문제를 해결한 후(conquer), 각각의 해를 결합시켜 전체 문제를 해결하는 알고리즘.
DynamicProgramming과의 가장 큰 차이점은 각각의 Subproblem이 모두 독립적이어서, 중복되는 것이 없다는 점이다. 만일 중복되는 것이 있다면, DynamicProgramming 기법을 적용함으로써 작업 속도면에서의 잇점을 얻을 수 있다.
Key Point ¶
이 알고리즘의 매력은, 전체 입력의 크기를 1/2, 1/3, 혹은 (1/2 or 1/3)로 나눠서 푼 것뿐인데, 결과적인 수행속도는 log로 줄어든다는 것이다. (log N)^n < N (for a big N)이라는 간단한 산수적인 사실이 이러한 알고리즘의 변환으로 막강한 수행속도의 개선을 이룬다는 것이다.
일상생활에서의 적용 ¶
- 여기서 반드시 고려해야 할 점은 데이터 사이즈가 N일 때, 그것을 나누는 횟수가 log N에 비례하는 것이 아니라, N에 비례할 경우에는 나눠봤자 아무 쓸모도 없다는 것과 Subproblem의 중복이 있을 때는 당연히 DynamicProgramming을 고려해야 한다는 사실에 주목해야 한다.
- 만약 해야할 일이 너무 덩치가 크다면, 일단 그 일이 완성되기 위해 이루어져야 할 작은 부분들을 생각한다. 이렇게 1차적으로 나눈 작은 부분들이 과연 "한 입"에 넣을 만큼 편한 크기인가, 만만한 크기인가 재어보고, 그렇지 않다면 다시 한번 나눈다. 이런 식으로 나누기를 계속해 나가다가 각각의 작은 작업이 모두 먹을만한 크기라고 여겨지면, 하나씩 각개 격파해 나간다. N차 단계의 답을 모두 얻었다면 이를 취합해서 N-1차 단계의 답을 조립하고, 다시 여기서 N-2차, ... 식으로 나가서 최종적으로 0차, 즉 원래의 문제에 대한 해결안을 구성한다.
원칙 ¶
- MECE (mutually exclusive, collectively exhaustive) : 각 subproblem을 해결한 후에 추가적인 작업을 하지 않기 위해서는 그전에 (많은 경우 힘들지만) correlation이 없도록 subprogram을 나누는 것이 중요하다. (mutually exclusive) 각 subprogram을 모두 풀었을 때 원래의 문제가 모두 커버되어야 하는 것은 물론이다. (collectively exhaustive)
.png ";)")
--