분할 정복과 병합 정렬

분할 정복

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘

• 다음과 같은 조건일 때 사용해봄직 하다.

  큰 문제와 쪼개진 문제가 동일하거나 비슷한 형태를 띌 때
  쪼개진 문제들간의 상관관계가 없을 때(서로 영향 X)

분할 정복의 장점

• 당연하게도 잘게 쪼개 해결함으로서 어려운 문제 해결 가능

• 병렬성 -> 쪼개진 문제들을 별개의 프로세서에서 실행 가능

• 캐시 친화적 -> 쪼개진 문제들이 충분히 작다면 메인 메모리에 접근하는 게 아닌 캐시 내에서 해결될 수 있기에 메모리 캐시를 효율적으로 사용하는 경향이 있음.

분할 정복의 단점

• 일반적으로 재귀를 많이 이용하는데, 이 때 메모리 사용이 커짐 -> 스택 오버플로 발생 가능성 존재

• 조건 설정이 어려움

병합 정렬

• 분할 정복의 가장 대표적인 예로서, 배열을 잘게 쪼갠후, 병합하며 정렬하는 정렬 알고리즘

• 직접 구현해보자(on python)

def rate(arr):
    if len(arr) == 1:
        return arr
    middle = len(arr)//2
    left = arr[:middle]
    right = arr[middle:]

    a = rate(left)
    b = rate(right)

    merged = []
    while len(merged) != len(arr):
        if a and b:
            if a[0] < b[0]:
                merged.append(a.pop(0))
            elif a[0] > b[0]:
                merged.append(b.pop(0))
            else:
                merged.append(a.pop(0))
        else:
            if a:
                merged.append(a.pop(0))
            else:
                merged.append(b.pop(0))

    return merged

잘게 나누고, 충분히 작게 나누어졌다면 병합을 시작한다.
병합할 두 배열의 첫 요소부터 서로 비교하면서, 작은 요소를 merged에 더해주고, 원래 배열에 있던 요소를 삭제한다. 이를 반복~