알고리즘: 분할 정복(Divide And Conquer) 예제 공부하기! (합병 정렬, 퀵 정렬)

분할 정복(Divide and conquer)이란?

 

 

어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어

 

해결하여 원래 문제의 해를 구하는 방식. 

 

 

 

분할 정복은 다음과 같은 절차를 거친다.  

 

1. Divide

  2개 이상의 작은 문제들로 쪼갠다. 

 

2. Conquer

  나누어진 작은 문제들을 푼다. 

 

3. Combine

  나누어 해결한 문제들을 합친다. 

 

 

 

1. 1부터 n까지의 합 (1 + 2 + 3 + ... + n)

 

def consecutive_sum(start, end):
    
    if start == end:
        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))

 

55
5050
32131
75466

 

1) Divide: 1 ~ n까지의 합을 절반씩 나눈다. 

 

2) Conquer: 절반씩 나눈 것들의 합 구한다. 

 

3) Combine: conquer에서 구한 값들을 모두 합친다. 

 

 

 

2. 합병정렬

 

 

정렬된 두개의 리스트를 파라미터로 하여 정렬된 하나의 리스트를 리턴하는 함수 merge()를 먼저 만든다.

 

def merge(list1, list2):
   
    if len(list1) < 1 or len(list2) < 1:
        return list2 + list1
        
        
    merged_list = []
   
    i = 0
    j = 0
    
    while i < len(list1) and j < len(list2):
        
        if list1[i] > list2[j]:             #list1 값과 list2 값을 차례로 비교하여 넣어준다.
            merged_list.append(list2[j])
            j += 1
            
        else:
            merged_list.append(list1[i])
            i += 1
            
            
            
    if i == len(list1):               # 남아있는 값은 나중에 한번에 넣어준다. 
        merged_list += list2[j:]
    else: 
        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]))

 

[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_sort() 안에서 리스트를 절반씩 divide한 후 전에 구현한 merge()를 이용해 합병정렬한다. 

 

def merge_sort(my_list):
    
    
    start = 0
    end = len(my_list) - 1
    
    
    if start == end: 
        return my_list
        
        
    mid = (start + end) // 2
    
    
    list1 = merge_sort(my_list[start: mid + 1])
    list2 = merge_sort(my_list[mid + 1: end + 1])
    
    
    
    return merge(list1, list2)
    
   


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]

 

1) Divide: merge_sort()안에서 리스트를 절반씩 나눈다. 

 

2) Conquer and combine: merge()를 이용해 절반씩 나눈 리스트들을 합쳐 정렬한다.  

 

 

 

3. 퀵 정렬

 

퀵 정렬을 구현하기 위해 파티션을 다음과 같이 나누자 

 

파티션 나누기(출처: 코드잇)

(파티션을 나누는 알고리즘은 유튜브를 참고하는게 좋다)

 

 

partition 함수를 다음과 같이 구현한다. 

 

# 두 요소의 위치를 바꿔주는 swap_elements()
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 = 0
    big_index = 0
    pivo = end
    
    
    while i < pivo + 1:
        
        if my_list[i] <= my_list[pivo]:
            
            swap_elements(my_list, big_index, i)
            big_index += 1
            
        i += 1
        
    pivo = big_index - 1 
    
    return pivo






list1 = [4, 3, 6, 2, 7, 1, 5]
pivot_index1 = partition(list1, 0, len(list1) - 1)
print(list1)
print(pivot_index1)


list2 = [6, 1, 2, 6, 3, 5, 4]
pivot_index2 = partition(list2, 0, len(list2) - 1)
print(list2)
print(pivot_index2)

 

[4, 3, 2, 1, 5, 6, 7]
4
[1, 2, 3, 4, 6, 5, 6]
3

 

 

quicksort 함수에서 partition함수를 반복적으로 구현한다. 

 

def quicksort(my_list, start = 0 , end = None):
   
    
    if end == None:   
        end = len(my_list) - 1
   
   
    if end - start < 1:  #base case
        return


    pivo = partition(my_list, start, end)
   
    quicksort(my_list, start, pivo - 1)  # pivo - 1 값이 음수가 될 수도 있으므로 base case를 조금 더 신경써주자 
    quicksort(my_list, pivo + 1, end)




list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1) 
print(list1)



list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2) 
print(list2)



list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3) 
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]

 

 

1) Divide: partition 함수를 구현하여 pivot 값을 기준으로 좌측에는 작은 값 우측에는 큰 값으로 나눈다.

(정렬되어 있지 않아도 상관없다)

 

2) Conquer and combine: quicksort 함수에서 partition을 반복적으로 이용하여 conquer and combine 해준다.