[알고리즘 algorithm] 분할 정복 divide and conquer 활용 예제

분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임이다.

- 대표적인 분할정복 알고리즘으로 병합정렬이 있다.
- 문제를 재귀로 쪼개 직접 해결할 수 있을 정도로 만든 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다.

분할 정복은 재귀 구조랑 거의 동일하며, 단지 넘겨주는 인자를 점점 분할하여 넘긴다. 이때 윈도우 슬라이싱이 잘 활용된다.


- 분할 정렬 : 대표적인 분할 정복 알고리즘

 

분할 과정)

긴 배열을 정렬해야 한다 => 어렵다. 쪼개자.

두 개의 배열로 쪼갬 => 여전히 어렵다. 더 쪼개자.

각각의 배열이 다시 2개로 쪼개져 총 4개의 배열이 됨. => 계속 쪼개자.

이런 방식으로 계속 진행하다보면 마지막에는 1개의 원소만을 가진 배열로 쪼개짐.

정복 과정)

이제 정복을 할 수 있다. 쪼개진 배열을 다시 조립하는 과정이라 생각하면 된다.

원소가 1개뿐인 배열의 값을 비교하여 작은 순서대로 붙인다. => 배열은 이제 원소가 2개가 되고, 원소는 정렬되있음.

또 원소 2개짜리 배열 2개를 합쳐서 원소 4개짜리 정렬된 배열로 만들자. 이때 합칠 때는 각 배열의 원소를 앞에서부터 비교해간다. 그러면서 값이 작은 순서대로 이어 붙여야 한다. 정렬 해야 하므로!

 

def merge(a, lo, hi):
    if lo == hi:
        return [a[lo]]

    mid = lo + (hi-lo)//2
    left = merge(a, lo, mid)
    right = merge(a, mid+1, hi)

    merged = []
    while left and right:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    return merged + left + right

- 분할 정복 활용 예제

문제: leetcode.com/problems/different-ways-to-add-parentheses/

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        values = []
        
        def compute(left,right,op):
            for l in left:
                for r in right:
                    values.append(eval(str(l)+op+str(r)))
               
        if expression.isdigit():
            return [int(expression)]
        
        for i in range(len(expression)):
            if expression[i] in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i+1:])
                compute(left,right,expression[i])
               
        return values