def recusion(num):
if num > 0:
#재귀함수: 자기 자신을 호출
return num * recusion(num -1)
else:
return 1 #0으로 하면 팩토리얼이기 때문에 값이 0 이 된다.
print(recusion(4))
24
def gcd(n1, n2):
if n1 % n2 == 0:
return n2
else:
return gcd(n2, n1%n2)
print(f'greatestCommonDevide(82,32) : {gcd(82,32)}')
greatestCommonDevide(82,32) : 2
생각할 점
원판 3개를 예로 들면
1. 위의 2개 원판을 경유기둥으로 옮긴다.
2. 마지막 원판을 도착기둥으로 옮긴다.
3. 경유기둥으로 옮긴 2개 원판을 도착 기둥으로 출발기둥을 경유해서 옮긴다.
#원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
else:
moveDisc(discCnt-1, fromBar, viaBar, toBar) # (discCnt-1)개들을 경유 기둥으로 이동
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!') # discCnt를 목적 기둥으로 이동
moveDisc(discCnt-1, viaBar, toBar, fromBar) # (discCnt-1)개들을 도착 기둥으로 이동
moveDisc(3, 1, 3, 2) #3개 원판을 1번기둥부터 3번 기둥으로 2번기둥을 경유해서 옮겨라.
1disc: 1에서 3(으)로 이동!
2disc: 1에서 2(으)로 이동!
1disc: 3에서 2(으)로 이동!
3disc: 1에서 3(으)로 이동!
1disc: 2에서 1(으)로 이동!
2disc: 2에서 3(으)로 이동!
1disc: 1에서 3(으)로 이동!
#병합정렬
#자료구조를 분할 하고 각각의 분할 된 자료구조를 정렬한 후 다시 병합하여 정렬한다.
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
righrIdx = 0
while leftIdx < len(leftNums) and righrIdx < len(rightNums):
if leftNums[leftIdx] < rightNums[righrIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx +=1
else:
mergeNums.append(rightNums[righrIdx])
righrIdx += 1
mergeNums = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[righrIdx:]
return mergeNums
nums =[8,1,4,3,2,5,10,6]
print(mSort(nums))
[1, 2, 3, 4, 5, 6, 8, 10]
mergeSortModuel.py
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)
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
mergeSort.py (실행파일)
import random
import mergeSortModuel as ms
rNums = random.sample(range(1,100),10)
print(f'not sorted rNums = {rNums}')
print(f'sorted rNums ASC: {ms.mSort(rNums)}')
print(f'sorted rNums DSC: {ms.mSort(rNums, asc=False)}')
not sorted rNums = [81, 42, 27, 91, 33, 95, 21, 6, 46, 16]
sorted rNums ASC: [6, 16, 21, 27, 33, 42, 46, 81, 91, 95]
sorted rNums DSC: [95, 91, 81, 46, 42, 33, 27, 21, 16, 6]
#퀵정렬
#기준 값 보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
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)}')
qSort(nums) : [1, 2, 3, 4, 4, 5, 6, 8, 8, 10]
quickSortModuel.py
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)
import random
import quickSortModuel as qs
rNum = random.sample(range(1,100),10)
print(f'not sorted Nums : {rNum}')
print(f'sorted Nums ASC : {qs.qSort(rNum)}')
print(f'sorted Nums DSC : {qs.qSort(rNum, asc=False)}')
not sorted Nums : [96, 69, 36, 89, 45, 32, 16, 23, 25, 78]
sorted Nums ASC : [16, 23, 25, 32, 36, 45, 69, 78, 89, 96]
sorted Nums DSC : [96, 89, 78, 69, 45, 36, 32, 25, 23, 16]