0429 알고리즘 2일차(~30)

재귀

자기 자신을 다시 호출하는 것

def recuision(num):

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

    else:
        return 1

recuision(10)

계속 자기 자신을 호출해가면서 0이 될때까지 함수가 이어짐

같은 방법으로 팩토리얼도 가능

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

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

재귀함수

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 greatestCommonDevide(n1,n2):

    maxNum = 0
    for i in range(1,(n1+1)):
        if n1% i == 0 and n2%i ==0:
            maxNum = i

    return maxNum

print(greatestCommonDevide(82,32))
print(greatestCommonDevide(96,40))

하노이의 탑(재귀함수 이용)

def moveDisc(discCnt, fromBar, toBar, viaBar):
    if discCnt == 1:
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동!')

    else:
        #(discNo-1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viaBar, toBar) #맨아래꺼 빼고 가는거라 -1

        #discCnt를 도착기둥으로 이동
        print((f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동!'))

        #{discCnt -1} 개들을 도착기둥으로 이동
        moveDisc(discCnt-1, viaBar,toBar,fromBar)

moveDisc(2,1,3,2)

moveDisc를 재귀함수로 사용해서 계속 자기 자신을 호출 /기둥들이 계속 바뀌면서 진행

병합정렬

자료구조 분할, 각각 분할된 자료구조 정렬한 후 다시 병합하여 정렬

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 mSort(ns,asc=True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns)//2  #분할
    leftNums = mSort(ns[0:midIdx],asc=asc)  #재귀함수 이용 / 재귀함수 들어갈 때, asc가 계속 True 호출됨
    rightNums = mSort(ns[midIdx:len(ns)],asc=asc)  #그걸 막기위해 asc=asc 추가

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

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

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx +=1
        else:
            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
    
import random as rd
import bunhal as sm

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

퀵정렬

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

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)
        elif n > midVal:
            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)}')