Python으로 알고리즘 분할 및 정복

Divide and Conquer(D&C)는 목표를 달성할 때까지 입력을 반으로 반복적으로 줄이는 데이터 구조 및 알고리즘에 대한 개념입니다. Divide and Conquer 알고리즘은 동적 프로그래밍에서 그리 멀지 않습니다. 둘 다 재귀적으로 입력 크기를 반으로 줄이지 만 차이점은 무언가를 계산하고 해당 변경 사항을 추적해야 하는 경우 동적 프로그래밍에서 메모이제이션을 사용하는 것이 좋습니다.

많은 분할 정복 알고리즘이 있으며 언제 사용해야 하는지, 어떻게 구현할 수 있는지 확인하겠습니다.

퀵소트

QuickSort는 이름에서 알 수 있듯이 정렬 알고리즘입니다. 나머지 입력 배열이 정렬되는 피벗 포인트를 선택합니다. 이 피벗은 배열의 첫 번째, 마지막 또는 가장 가운데에 있는 요소가 될 수 있습니다. 런타임은 피벗 포인트를 무엇으로 선택하느냐에 따라 크게 달라질 수 있습니다.

GeeksForGeeks의 파이썬 예제

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 

    for j in range(low , high): 

        if   arr[j] < pivot: 

            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

def quickSort(arr,low,high): 
    if low < high: 

        pi = partition(arr,low,high) 

        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

이진 검색

이 검색 알고리즘은 내가 분할 정복을 볼 때 생각하는 첫 번째 알고리즘입니다. 이 알고리즘은 입력 배열이 이미 정렬된 경우에만 작동합니다. 우리는 입력 배열과 찾고 있는 원하는 숫자를 받습니다. 그런 다음 배열에서 가장 가운데에 있는 요소와 비교합니다. 원하는 요소가 가장 가운데 있는 요소보다 작으면 배열의 위쪽 절반을 잘라내고 프로세스를 반복합니다. 만약 우리의 요소가 가장 가운데에 있는 요소보다 크다면 배열의 더 큰 요소만 보고 반대를 합니다.

유사 예

def binarySearch(arr, desiredNum):
     mid = arr.length/2

     if(desiredNum > arr[mid])
          look at first half of array
          reset mid within scope of array
          repeat search
     else
          look at bigger half of array
          reset mid within scope of array
          repeat search
return index of element

병합 정렬

병합 정렬은 전체 배열이 모두 분할될 때까지 둘로 분할한 다음 천천히 함께 정렬하기 시작하는 매우 멋진 정렬 알고리즘입니다.

GeeksForGeeks의 의사 코드

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)