(중급) 재귀(Recursive) 알고리즘, 하노이(Hanoi), 정렬

🔑Summarization

---

• 재귀(Recursive) 알고리즘
• 하노이의 탑
• 병합정렬, 퀵 정렬

---

📗Contents

---

• 재귀(Recursive) : 나 자신을 다시 호출하는 것

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

recusion(10)

# factorial

def factorial(num):
    if num > 0:
        return num * factorial(num - 1)
    else:
        return 1

print(f'factorial(10): {factorial(10)}')

• 유클리드 호제법
  • 두 자연수 $n1$, $n2$에 대하여 $(n1 > n2)$ $n1$를 $n2$로 나눈 나머지를 $r$이라고 할 때, $n1$과 $n2$의 최대공약수는 $n2$와 $r$의 최대공약수와 같다.

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

• 하노이의 탑
  • 퍼즐 게임의 일종
  • 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같음
    1. 한 번에 한 개의 원판만 옮길 수 있다.
    2. 큰 원판이 작은 원판 위에 있어서는 안된다.

• Ex) 원판 갯수 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 += leftNums[leftIdx:]
    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)}')