재귀 알고리즘

나 자신을 다시 호출하는 것

def recusion(num):

    if num > 0:
        print('*' * num)
        return recusion(num-1)
    else:
        return 1
    
recusion(10)
**********
*********
********
*******
******
*****
****
***
**
*

하노이의 탑

def moveDisc(discCnt, fromBar, toBar, viaBar):
          # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
    if discCnt == 1:
        print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')

    else:
    	# (discNo-1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viaBar, toBar)              
        
        # discNo를 목적 기둥으로 이동
        print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!') 
        
        # (discNo-1)개들을 도착 기둥으로 이동
        moveDisc(discCnt-1, viaBar, toBar, fromBar)

moveDisc(3, 1, 3, 2)

병합정렬

자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다.

def mSort(ns):
    
    if len(ns) < 2:
        return ns
    
    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx])
    rightNums = mSort(ns[midIdx:len(ns)])

    mergeNums = []
    leftIdx = 0; rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1

        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1

    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums

nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mSort(nums) : {mSort(nums)}')

퀵 정렬

기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

def qSort(ns):

    if len(ns) < 2:
        return ns
    
    midIdx = len(ns) // 2
    midVal = ns[midIdx]


    smallNums = []; sameNums = []; bigNums = []

    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)
    
    return qSort(smallNums) + sameNums + qSort(bigNums)

nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'qSort(nums) : {qSort(nums)}')

이글은 제로베이스 데이터 취업스쿨의 강의자료 일부를 발췌하여 작성되었습니다.