[알고리즘] 004_재귀

✏️ 재귀 알고리즘

• 나 자신을 다시 호출하는 것
• 이론은 어렵지만, 이해하면 간단하게 코드 작성 가능
• 예시 ) 팩토리얼, 하노이의 탑 (코딩 기출 문제)

💡 팩토리얼

def factorial(num) :
	if num > 0 :
    	return num * factorial(num)
    else :
    	return 1
        
print(factorial(숫자입력))

💡 유클리드 호제법

두 자연수 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(gcd(n1입력,n2입력))

💡 하노이의 탑

이해는 잘안돼서 연습을 해봐야하는 부분ㅠ

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

	if disCnt == 1 :
    	print(f'{discCnt}disc 중 {fromBar}에서 {toBar}로 이동!')
    
    else :
    	# (discNo -1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viabar, toBar)
        # discCo를 목적 기둥으로 이동
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}로 이동!')
        
        # (discNo-1)개들을 도착 기둥으로 이동
        moveDisc(discCnt-1, viabar, toBar, fromBar)
        
# 아래 숫자는 예시값
moveDisc(3,1,3,2)

✏️ 재귀 알고리즘을 활용한 "정렬"

💡 병합정렬

• 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬
  이해는 잘안돼서 연습을 해봐야하는 부분ㅠ

#오름차순 정렬
def mSort(ns, asc=True) :

	if len(ns) < 2 :   #ns가 하나가 나올때까지
    	return ns
        
    #분할 단계
    midIdx = len(ns) // 2 #중간위치
	leftNums = mSrot(ns[0:midIdx], asc=asc)
    rightNums = mSrot(ns[midIdx:len(ns)],asc=asc)
    #asc=asc : 앞에걸 그대로 적용한다는 뜻이라는 데 뭐라는지 모르겠담...ㅠㅠ(참고로 chapter 3, 28강임)
    
    #병합하는 단계
    mergeNums = []
    leftIdx = 0 ; rightNums = 0   #임의 지정
    while leftIdx < len(leftNums) and rightIdx < len(rightNums) :
    	if asc =True :
    		if leftNums[leftIdx] < rightNums[rightIdx] :
        		mergeNums.appen(leftNums[leftIdx])
            	leftIdx += 1
        	else :
        		mearNums.append(rightNums[rightIdx])
            	rightIdx += 1
        else :   #asc=False일 경우,
        	if leftNums[leftIdx] > rightNums[rightIdx] :
        		mergeNums.appen(leftNums[leftIdx])
            	leftIdx += 1
        	else :
        		mearNums.append(rightNums[rightIdx])
            	rightIdx += 1
        
    mergeNums = mergeNums + lefNums [leftIdx : ]
    mergeNums = mergeNums + rightNums [rightIdx : ]
    
    return MergeNums
    
nums = [0,1,4,3,2,5,10,6]
print(mSort(nums))

💡 퀵 정렬

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

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 : #asc=True 로 설정
    	return qSort(smallNums,asc=asc) + sameNums + qSort(bigNums,asc=asc)
    else : 
    	return qSort(bigNums,asc=asc) + sameNums + qSort(smallNums,asc=asc)
    
nums=[8,1,4,3,2,5,4,10,6,8]
print(qSort(nums))
print(qSort(nums, asc=False))