분할정복(Divide and Conquer)이 무엇인가?

개요

여러 알고리즘의 기본이 되는 해결방법으로,

 

기본적으로는 엄청나게 크고 방대한 문제를

조금씩 조금씩 나눠가면서 용이하게 풀 수 있는

문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.

 

대표적으로는 퀵소트나 병합정렬이 있다.

그림에서와 같이 분할 정복은

상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태로 도식화 할 수 있다.

• 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

 

 

적용방식

분할 정복법은 재귀적으로 자신을 호출하면서

그 연산의 단위를 조금씩 줄어가는 방식이다.

분할 정복의 프로세스는 대체로 아래와 같다.

function F(x):
  if F(x)가 간단 then:
    return F(x)를 계산한 값
  else:
    x 를 x1, x2로 분할
    F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

한 마디로 "F(x)가 간단"이라는 조건을 만족할 때까지

문제를 쪼개고 쪼개서 값을 구하자는 것이다.

 

단점

함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며,

스택에 다양한 데이터를 보관하고 있어야 하므로 

 

스택오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다. 

가장 중요한 것은 이 알고리즘의 핵심인 "F(x)가 간단"이 어떤 것이냐에 따라

알고리즘의 퍼포먼스가 생각보다 꽤 차이나게 된다는 것이다.

 

이 "F(x)가 간단하다"라는 것을 정의하는 것의 난해함 역시 단점 중에서 중요하게 다루어지고 있다.

 

 

[1] 대표적으로 병합 정렬의 시간복잡도는 O(n log n)이다.

[2] 일반적으로 메모이제이션을 사용함으로써 해결한다.

바킹독 시간복잡도

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

 

----출처 : 나무위키

 

챗gpt에게 물어보았다.