진행자

장하늘

분할정복이란?

‘분할정복’이란 말 그대로 분할 될 수 있는 큰 문제를 분할하여 해결한 후 조합하여 해결하는 방법.

작게 분할된 문제들은 원래 문제와 동일한 형태를 가지며 큰 문제의 부분이 된다.

• 비슷한 문제 해결방식을 가진 다이나믹 프로그래밍과의 차이는 무엇일까?

분할정복

• 재귀를 이용하여 구현
• 부분문제들이 서로 독립적인 관계
• 정렬 알고리즘 등에 유리

다이나믹 프로그래밍

• 반복문을 이용하여 구현
• 부분 문제들이 서로 종속적인 관계
• 최단 경로 문제 등에 유리

분할정복 구성 단계

• Divide

  큰 문제를 비슷한 유형의 하위 문제로 최대로 분할한다.
  

• Conquer

  하위 문제를 재귀적으로 해결한 후, 더 이상 나눠지지 않으면 탈출한다.
  

• Combine

  Conquer 단계에서 해결된 문제들을 통합하여 해결한다.
  

대표적인 예시

분할정복의 장단점

장점

1. 빠른 속도

• 분할적인 문제 풀이로 큰 문제를 빠르게 해결

2. 쉬운 병렬화

• 부분 문제들을 병렬 처리하여 멀티코어 시스템에서 좋은 성능

3. 유연성

• 여러 분야에 응용가능하며 복잡도와 데이터 크기에 상대적으로 유연함.

단점

1. 메모리 요구

• 부분 문제들의 재귀적인 호출로 추가적인 메모리 요구

2. 시간복잡도

• 정렬문제의 경우 잘못 구현 시 기하적인 시간복잡도 요구

3. 구현 복잡성

• 구현하기 까다로운 조건 요건 존재

알고리즘 구현

백트래킹이란?