알고리즘 이론

알고리즘

Divide and Conquer(분할 정복 방식)

• 알고리즘에서 어려운 축에 속하는 방식으로 divide(분할), conquer(정복), combine(결합) 이 세가지의 단계로 진행이 된다. 그리고 주로 '재귀 함수'가 많이 사용이 된다.

합병 정렬(Merge sort)

• 두 리스트를 정렬된 상태로 합치는 것을 의미한다.
• 두 리스트에서 순서대로 차례로 값을 추출 한 뒤, 비교해 작은 값을 새로운 합병 리스트에 넣어준다. 만약 추가되면 그 다음 값을 추출하고 추가되지 못한 값은 계속 있는다. 이런식으로 차례대로 추가해 새로운 리스트를 만드는 방식으로 정렬한다.

1. 합병 정렬에서 사용되는 Merge 함수를 구현 해준다.

def merge(list1, list2):
    i = 0              
    j = 0
    merged_list = []  -> 합병된 리스트를 정의
    
    while i < len(list1) and j < len(list2):
        if list[i] < list[j]:
            merged_list.append(list1[i])
            i += 1
        elif list[i] > list[j]:
            merged_list.append(list2[j])
            j += 1
         
        리스트에 넣어준 후 나머지 값들을 리스트에 추가해
        if i == len(list1):
            merged_list += list2[j:]
        elif j == lend(list2):
            merged_list += list1[i:]
        
        return merged_list

2. 합병 정렬 함수 구현하기

2-1 divide 과정 - 큰 리스트를 반으로 쪼개는 과정을 진행

left_half = my_list[:len(my_list)//2]
right_half = my_list[len(my_list)//2:]

2-2 conquer, combine 과정

return merge(merge_sort(left_half), merge_sort(right_half))

합병정렬 구현하기

def merge(list1, list2):
    i = 0              
    j = 0
    merged_list = []  -> 합병된 리스트를 정의
    
    while i < len(list1) and j < len(list2):
        if list[i] < list[j]:
            merged_list.append(list1[i])
            i += 1
        elif list[i] > list[j]:
            merged_list.append(list2[j])
            j += 1
         
        리스트에 넣어준 후 나머지 값들을 리스트에 추가해
        if i == len(list1):
            merged_list += list2[j:]
        elif j == lend(list2):
            merged_list += list1[i:]
        
        return merged_list
        
def merge_sort(my_list):
    if len(my_list) < 1:    -> base case 리스트의 값이 1개 혹은 0일때 바로 나옴
        return my_list
        
        
    left_half = my_list[:len(my_list)]     -> divide 과정
    right_half = my_list[len(my_list):]
   
   return merge(merge_sort(left_half), merge_sort(right_half)) - > conquer, combine 과정

출처 - codeit(알고리즘)