분할정복, Divde / Conquer / Combine

 

 

정의 :

- 주어진 문제를 2개 이상의 유사한 하위 문제로 분할하여, 각 하위 문제에 대한 해결 이후, 해결들을 합쳐 처음 문제를 해결하는 방법

---

특징 :

- 하위 문제로 나뉘어진 각 문제들은, 서로에게 독립적이며 중복되지 않는다.

- 주어진 문제와 이를 나눈 하위 문제들은, 해결 방법이 동일하다.

---

장점 :

- 빠르고 간편하다. 분할 이후 해결 방법이 동일하기 때문에, 코드 구현 시 하나의 해결 방법만 제시하면 된다.

- 하위 문제가 독립적이기 때문에 병렬적으로 문제를 처리할 수 있으므로, 시간을 효율적으로 처리할 수 있다.

---

단점 :

- 분할과 하위 문제 해결에 재귀적인 함수 호출이 일어나게 되어, 메모리 사용량이 증가한다.

- 스택 과다 사용으로 인한 높은 메모리 사용이 발생할 수 있다.

---

Dynamic Programming , 분할정복

- DP와 분할정복은 큰 문제를 작은 문제로 분할한 이후 각 문제의 해결을 통해 큰 문제의 해결이 가능하다는 공통점이 있다.

- DP는 분할 이후 하위문제들이 중복되며, 각 하위문제에 대해 의존적인 성질이 있다.

- 이로 인해 메모이제이션을 통한 효율적인 연산을 목표로 한다.

 

DP, 피보나치 수열

 

분할정복, 병합 정렬

---

예시 :

하노이의 탑

def hannoi(n, a, b):
    if n == 1:
        print(a, b)
        return
    hannoi(n - 1, a, 6 - a - b)
    print(a, b)
    hannoi(n - 1, 6 - a - b, b)


n = int(input())
print(2**n - 1)

if n <= 20:
    hannoi(n, 1, 3)

 

 

퀵 정렬

numbers = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort (arr, left, right) :
    
    if len(arr) < 2 :
        return arr
    
    pl = left
    pr = right
    pivot = arr[(left + right) // 2]
    
    while pl <= pr :
        while arr[pl] < pivot :
            pl += 1
        while arr[pr] > pivot :
            pr -= 1
        if pl <= pr :
            arr[pl], arr[pr] = arr[pr], arr[pl]
            pl += 1
            pr -= 1
            
    if left < pr :
        quick_sort(arr, left, pr)
    if pl < right :
        quick_sort(arr, pl, right)
        
quick_sort(numbers, 0, len(numbers) - 1)
print (numbers)

 

 

이진 검색 트리

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

arr = []

while True :
    try :
        a = int(input())
        arr.append(a)
    except :
        break
            
    

def search (list) :
    
    if not list :
        return
    
    root = list[0]
    left, right = [], []
    
    for i in list[1:] :
        if i > root :
            right.append(i)
        else :
            left.append(i)
            
    search (left)
    search (right)
    print (root)


search (arr)