제로베이스 알고리즘(23~30)

1. 재귀
나 자신을 다시 호출하는 것

def recursion(num):

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

recursion(10)

2. 하노이의 탑
퍼즐게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기는 것
한 번에 한 개의 원판만 옮길 수 있음
큰 원판이 작은 원판 위에 있어서는 안됨

#           원판개수, 출발기둥, 도착기둥, 경유기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):

    if discCnt == 1:
        print(f'{discCnt}Disc를 {fromBar}에서 {toBar}로 이동')

    else:
        moveDisc(discCnt-1, fromBar, viaBar, toBar)

        print(f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동')

        moveDisc(discCnt-1, viaBar, toBar, fromBar)

moveDisc(3, 1, 3, 2)

3. 병합정렬
자료구조를 분할하고 분할된 자료구조를 정렬한 후 다시 병합하여 정렬
재귀함수로 넘어갈 때 매개변수가 누락될 수 있으므로 주의

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)}')

4. 퀵정렬
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합침

import random as rd

def qSort(ns, asc=True):

    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)
        elif n > midVal:
            bigNums.append(n)

    if asc:
        return qSort(smallNums) + sameNums + qSort(bigNums)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

rNums = rd.sample(range(1, 101), 10)
print(rNums)
print(f'qSort rNums : {qSort(rNums, False)}')