[Algorithm] 분할정복 이론 + 예제

❗분할정복이란?

문제를 작은 하위 문제로 나누고 각각의 하위 문제를 재귀적으로 해결한 뒤, 그 해답을 결합하여 원래 문제를 해결하는 방법이다.

 

❗분할정복 기본 원리

 

1. 분할 (Divide):
   • 문제를 더 작은 하위 문제로 나눈다.
   • 문제를 동등한 크기의 여러 하위 문제로 분할한다.
2. 정복 (Conquer):
   • 각 하위 문제를 재귀적으로 해결한다.
   • 하위 문제들이 충분히 작아지면 재귀적으로 해결할 수 있으며 이를 기저 조건이라고 한다.
   • 기저 조건에서는 하위 문제를 더 이상 분할할 수 없는 상태에 도달한다.
3. 합병 (Combine):
   • 각각의 하위 문제에서 나온 해답을 합쳐 원래 문제의 해답을 구성한다.

 

❗예제

result = ""  

# 현재 영역이 모두 같은 숫자로 이루어져 있는지 확인하는 함수
def all_same(x, y, size):
    standard = graph[x][y]  
    for i in range(x, x + size):
        for j in range(y, y + size):
            if graph[i][j] != standard:  
                return False
    return True



def div_and_conq(x, y, size):
    global result

	# 기저 조건
    if all_same(x, y, size):
        result += str(graph[x][y])
        return
    
    result += "("  
    half_size = size // 2 

    for i in range(2):
        for j in range(2):
        	# 해당 영역을 다시 분할
            div_and_conq(x + i * third_size, y + j * third_size, third_size)
            
    result += ")"


div_and_conq(0, 0, n)


print(result)