[알고리즘] 분할정복(Divide Conquer)

말 그대로 큰 문제를 재귀적으로 쪼개어 나간 다음 하위문제들의 결과를 조합 해 원래 문제의 결과를 도출하는 방식.

분할 -> 정복 -> 조합

3단계로 이루어지며 대표적으로 병합 정렬 알고리즘을 볼 수 있다.

def F(X):
    # 정복
    if F(X)가 간단해졌을 때:
        return F(X)계산값(int or list or str)

    else:
        # 분할
        X를 left와 right로 분할.
        F(left)와 F(right)를 호출
        # 조합
        return F(left)와 F(right)로 F(x)를 구하는 관계식(재귀)

추후 최적 부분구조(Optimal Substructure)에도 연관 됨.

예제로 연산 문자열이 들어갔을 때 괄호를 치는 경우의 수에 따른 계산값 리스트를 구하는 함수.

 

각 연산자를 만남에 따라 좌우를 나누어 계산 결과를 가져오도록 재귀시킴.

class Solution:
	#정복1
    def diffWaysToCompute(self, input: str) -> List[int]:
        def operation(le, ri, oper):
            sm = 0
            result = []
            for l in le:
                for r in ri:
                    if oper == "+":
                        sm = l + r
                    elif oper == "-":
                        sm = l - r
                    elif oper == "*":
                        sm = l * r
                    result.append(sm)
            return result
        results = []

        # 정복2
        if input.isdigit():
            return [int(input)]

        # 분할위치 선정.
        for i in range(len(input)):
            if input[i] in '+-*':
                # 현재 연산자 기준으로 분할
                left = self.diffWaysToCompute(input[:i])
                right= self.diffWaysToCompute(input[i + 1:])

                # 병합.(left right로 diffwayTocompute의 results를 구함.)
                results.extend(operation(left, right, input[i]))
        return results