- 하노이의 탑 (재귀함수 이용)
- 퍼즐게임의 일종으로, 세 개의 기둥을 이용해서 원판을 전부 다른 기둥으로 옮기면 되는 게임
- 제약조건 : 한 번에 한 개의 원판만 옮길 수 있음. 큰 원판이 작은 원판 위에 있어서는 안 됨.
-> 가장 큰 원판 빼고 나머지 원판들부터 보조기둥으로 옮긴 후, 가장 큰 원판을 비어있는 기둥 맨 밑바닥에 놓기 -> 나머지 원판들을 옮길 때에도 그중 가장 큰 원판을 밑바닥에 놓기 위해 작업
-> 재귀함수 이용!
# 원판개수, 출발기둥, 도착기둥, 경유기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')
else:
# (discCnt-1) 원판들을 경유기둥으로 이동 # 가장 큰 원판(discCnt)를 도착기둥에 놓기 위해 도착기둥을 비워두고 나머지 원판들을 전부 경유기둥으로 이동
moveDisc(discCnt-1, fromBar, viaBar, toBar)
# discCnt를 도착기둥으로 이동
print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')
# (discCnt-1) 원판들을 도착기둥으로 이동 # 경유기둥에 있던 기둥들을 이동시킴
moveDisc(discCnt-1, viaBar, toBar, fromBar)
moveDisc(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(으)로 이동!- 병합 정렬 (재귀함수 이용)
- 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후, 다시 병합하여 정렬함
- 반으로 자르고, 자르고를 반복해서 자료 한 개씩 분할 후, 1+1, 2+2, 4+4 식으로 자료를 병합하고 정렬하고, 그걸 다시 병합하고 정렬하기를 반복함
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]: # 왼쪽, 오른쪽 숫자를 비교하여 왼쪽이 작으면 리스트에 그 숫자를 추가하고 인덱스+1, 오른쪽이 작으면 그 숫자를 리스트에 추가하고 인덱스+1해서 다음 숫자를 비교
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=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- 실행파일
import random
import sortMod as sm
rNums = random.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)}')- 오름차순, 내림차순 옵션 주기 (모듈 만들어 사용)
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 as rd
import sortMod as sm
rNums = rd.sample(range(1, 100), 10)
print(f'not sorted rNums: {rNums}')
print(f'sorted rNums ASC: {sm.qSort(rNums)}')
print(f'sorted rNums DESC: {sm.qSort(rNums, asc=False)}')<제로베이스 데이터 취업 스쿨>
