19번째 알고리즘 6~7 스터디 노트

내용요약

재귀: 재귀함수, 하노이의 탑
정렬: 병합정렬, 퀵정렬

재귀

• 재귀 알고리즘
  나 자신을 다시 호출하는 것을 재귀라고 한다.
  

# 실습 유클리드 호제법
def gcd(n1, n2):

    if n1 % n2 == 0:
        return n2
    else:
        return gcd(n2, n1 % n2)

print(f'gcd(82, 32): {gcd(82, 32)}')
print(f'gcd(96, 40): {gcd(96, 40)}')

• 하노이의 탑
  퍼즐게임의 일종으로 세개의 기둥을 이용해서 제약 조건을 지키며 원판을 다른 기둥으로 옮기는 게임
  

# 실습 하노이의 탑 게임 진행과정 출력
def moveDisc(discCnt, fromBar, toBar, midBar):                    # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
    if discCnt == 1:
        print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')

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

moveDisc(3, 1, 3, 2)

정렬

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

# 실습 실행 파일
import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print(f'not sorted rNums: {sm.mSort(rNums)}')
print(f'merge sorted rNums by ASC: {sm.mSort(rNums)}')
print(f'merge sorted rNums by DESC: {sm.mSort(rNums, asc=False)}')

# 병합정렬 모듈
def mSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

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

        if asc:

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

        else:

            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergedNums = mergedNums + leftNums[leftIdx:]
    mergedNums = mergedNums + rightNums[rightIdx:]
    return mergedNums

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

# 실습 실행파일
import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print(f'not sorted rNums: {sm.qSort(rNums)}')
print(f'merge sorted rNums by ASC: {sm.qSort(rNums)}')
print(f'merge sorted rNums by DESC: {sm.qSort(rNums, asc=False)}')

# 퀵정렬 모듈
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)
        else:
            bigNums.append(n)

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

후기

재귀함수를 이해하는게 오래 걸렸는데 이해하고 나면 어렵지 않은 느낌인데 혼자 적용하기는 어렵다. 적용했을때 효율적인 방법이라 응용할 생각을 많이 해야하는 부분인것 같다.

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