[Algorithm] Divide and Conquer

2025.03.15 - [프로그래밍/Python 관련 정보] - [Python] Table of Contents

---

분할 정복은 가장 일반적인 형태의 문제 해결 방법론입니다. 문제를 더 이상 나눌 수 없을 때까지 작은 하위 문제(Sub-problem)로 나누고, 이를 각각 해결한 뒤 합쳐서 원래 문제의 답을 얻습니다.

• Divide: 원래 문제를 서로 겹치지 않는(Disjoint) 하위 문제들로 분할합니다.
• Conquer: 하위 문제를 재귀적으로 해결합니다.
• Combine: 하위 문제의 해를 결합하여 원래 문제의 해를 구합니다.

일반적으로 재귀(Recursion)를 사용하며, 시간 복잡도는 마스터 정리(Master Theorem)를 따르는 경우가 많습니다.

Dynamic Programming, Greedy Algorithm과 구별되는 개념이라기 보다는 좀 더 추상적인 문제 해결 전략으로 이해하면 될 것 같습니다. 직관적인 이미지는 이렇습니다.

 

• Divide and Conquer → “나누고 각각 해결”
• Dynamic Programming → “나누되, 겹치면 기억”
• Greedy → “전체를 보지 않고 지금 최선만 선택”

 

아주 간단한 케이스 (1~n까지의 합) 예시를 먼저 보면

def consecutive_sum(start, end):
    # 여기에 코드를 작성하세요
    if start==end:
        return start
    mid = (start+end)//2
    return consecutive_sum(start, mid)+consecutive_sum(mid+1, end)

 

 

그런데, 사실 combine단계에서 까다로운 경우도 있습니다. 추후 기회가 되면 추가하도록 하겠습니다.