TIL_23 : Divide and Conquer

🙄 Divide and Conquer

---

➡ Divide and Conquer?

• 분할 정복, 아래 3단계로 구성

1. Divide : 답을 바로 알아내기 어려운 큰 문제를
2. Conquer : 여러 부분 문제로 나누고
3. Combine : 부분문제의 답을 결합해 큰 문제 해결

➡ Divide and Conquer 예시

• 1부터 n까지의 합

def consecutive_sum(start, end):
    mid = (start + end) // 2
    if start < mid:
        return consecutive_sum(start, mid) + consecutive_sum(mid, end) - mid
    elif start == mid:
        return start + end
    elif mid + 1 == end:
        return end
    
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))

# 55
# 5050
# 32131
# 75466

🙄 합병 정렬 (Merge Sort)

---

➡ 합병 정렬?

1. Divide : 리스트를 반으로 나눈다
2. Conquer : 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한다
3. Combine : 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다

➡ 합병 정렬 예시

# Combine을 돕는 함수 
def merge(list1, list2):
    i = 0
    j = 0
    merged_list = []
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j]:
            merged_list.append(list2[j])
            j += 1
        else:
            merged_list.append(list1[i])
            i += 1
    if i == len(list1):
        merged_list += list2[j:]
    elif j == len(list2):
        merged_list += list1[i:]
    return merged_list
 
 
# 합병 정렬
def merge_sort(my_list):
    if len(my_list) == 1:
        return my_list
        
    mid = len(my_list) // 2
    split1 = merge_sort(my_list[:mid])
    split2 = merge_sort(my_list[mid:])
    
    sort_list = merge(split1, split2)
    return sort_list

# 테스트
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))

# [1, 3, 5, 7, 9, 11, 11, 13]
# [1, 5, 7, 9, 13, 15, 28, 30, 48]
# [1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]

🙄 퀵 정렬 (Quicksort)

---

➡ 퀵 정렬?

• Partition : Pivot(기준점)을 정한다

1. Divide : Pivot을 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽에 둔다.
2. Conquer : Pivot 왼쪽과 오른쪽을 각각 정렬
3. Combine : 할 일이 없음, Divide와 Conquer 단계만 거치면 정렬 완성

➡ 퀵 정렬 예시

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    i = start
    b = start
    p = end
    while i < p:
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1
    swap_elements(my_list, b, p)
    p = b
    return p

# 퀵 정렬 
def quicksort(my_list, start = 0, end = None):
    if end == None:
        end = len(my_list) - 1
    if end - start < 1:
        return
    pivot = partition(my_list, start, end)
    quicksort(my_list, start, pivot - 1)
    quicksort(my_list, pivot + 1, end)

# 테스트 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1) # start, end 파라미터 없이 호출
print(list1)

# 테스트 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2) # start, end 파라미터 없이 호출
print(list2)

# 테스트 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3) # start, end 파라미터 없이 호출
print(list3)

# [1, 3, 5, 7, 9, 11, 11, 13]
# [1, 5, 7, 9, 13, 15, 28, 30, 48]
# [1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]