재귀: 재귀함수, 하노이의 탑
정렬: 병합정렬, 퀵정렬
# 실습 유클리드 호제법
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)
재귀함수를 이해하는게 오래 걸렸는데 이해하고 나면 어렵지 않은 느낌인데 혼자 적용하기는 어렵다. 적용했을때 효율적인 방법이라 응용할 생각을 많이 해야하는 부분인것 같다.
이글은 제로베이스 데이터 취업스쿨의 강의자료 일부를 발췌하여 작성되었습니다.