알고리즘 패러다임 / Divide and Conquer [1/2]

 

알고리즘 패러다임 / Divide and Conquer

 

 

Divide and Conquer (분할 정복) : 하나의 문제를 해결하기 위해 여러 가지 부분문제로 나누고 부분문제들을 정복한 뒤 부분문제들을 합쳐서 문제를 해결한다.

 

(문제를 정복하다 : 문제에 대한 답을 알아내다)

def consecutive_sum(start, end):
    if end == start:
        return start
    
    mid = (start + end) // 2
    return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)

# 테스트
print(consecutive_sum(1, 10))
print(consecutive_sum(1, 100))
print(consecutive_sum(1, 253))
print(consecutive_sum(1, 388))

#<Run>
#55
#5050
#32131
#75466

Divide and Conquer - 1부터 n까지의 합

---

합병 정렬 : Divide and Conquer 알고리즘 중 하나로 정렬할 하나의 리스트를 반으로 나눠서, 나눠진 리스트들을 정렬하여 합친다.

 

합병 정렬 진행 과정

 

[16, 11, 6, 13, 1, 7, 10, 4] 라는 리스트가 있다고 하자. 여기서 반씩 나누면

[16, 11, 6, 13], [1, 7, 10, 4] 이렇게 두 개로 나뉘어진다. 아직 바로 문제를 정복할 수 없으므로 각각 반씩 또 나누면

[16, 11], [6, 13], [1, 7], [10, 4] 이렇게 나누어진다. 아직 리스트가 충분히 작지 않아서 재귀적으로 또 반씩 나누어주면

[16], [11], [6], [13], [1], [7], [10], [4] 이렇게 나누어진다. 이제 정복된 두 개의 답을 가지고 합쳐준다.

[11, 16], [6, 13], [1, 7], [4, 10] 이렇게 합쳐진다. 여기서 또 합쳐야하는데 모든 리스트가 정렬된 상태이니 왼쪽 작은값부터 값의 대소를 비교하여 합쳐준다.

[6, 11, 13, 16], [1, 4, 7, 10] 이렇게 합쳐지고 마지막으로 합쳐주면

[1, 4, 6, 7, 10, 11, 13, 16] 의 정렬된 리스트가 완성되었다.

---

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 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

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list

# 테스트
print(merge([1],[]))
print(merge([],[1]))
print(merge([2],[1]))
print(merge([1, 2, 3, 4],[5, 6, 7, 8]))
print(merge([5, 6, 7, 8],[1, 2, 3, 4]))
print(merge([4, 7, 8, 9],[1, 3, 6, 10]))

#<Run>
#[1]
#[1]
#[1, 2]
#[1, 2, 3, 4, 5, 6, 7, 8]
#[1, 2, 3, 4, 5, 6, 7, 8]
#[1, 3, 4, 6, 7, 8, 9, 10]

합병 정렬 알고리즘 - merge 함수

 

merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴한다.

---

def merge(list1, list2):
    i = 0
    j = 0

    # 정렬된 항목들을 담을 리스트
    merged_list = []

    # list1과 list2를 돌면서 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

    # list2에 남은 항목이 있으면 정렬 리스트에 추가
    if i == len(list1):
        merged_list += list2[j:]

    # list1에 남은 항목이 있으면 정렬 리스트에 추가
    elif j == len(list2):
        merged_list += list1[i:]

    return merged_list


def merge_sort(my_list):
    # base case
    if len(my_list) < 2:
        return my_list

    # my_list를 반씩 나눈다(divide)
    left_half = my_list[:len(my_list)//2]    # 왼쪽 반
    right_half = my_list[len(my_list)//2:]   # 오른쪽 반

    # merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
    # merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
    return merge(merge_sort(left_half), merge_sort(right_half))

# 테스트
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]))

#<Run>
#[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]

합병 정렬 알고리즘 - 합병 정렬 구현하기

 

merge 함수를 이용하여 merge_sort 함수 써 보기. merge_sort 는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴한다.