하노이의 탑
하노이의 탑이란?
퍼즐 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다.
하노이의 탑(실습)
실습
파이썬을 이용해서 하노이의 탑 게임 진행 과적을 출력해보자!
# discCnt: 원판 개수, fromBar: 출발 기둥, toBar: 도착 기둥, viaBar: 경유 기둥
# 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
if discCnt == 1:
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
else:
# (discCnt-1) 개들을 경유 기둥으로 이동
moveDisc(discCnt-1, fromBar, viaBar, toBar) # (disCnt-1)개를 출발 기둥에서 viaBar(경유지 기둥)로 도착, toBar(도착 기둥)를 경유해서
# discCnt를 목적 기둥으로 이동
print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')
# (discCnt-1) 개들을 도착 기둥으로 이동
moveDisc(discCnt-1, viaBar, toBar, fromBar)
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; 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)}')결괏값:
mSort(nums): [1, 2, 3, 4, 5, 6, 8, 10]병합정렬(실습)
실습
1부터 100까지 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자.
모듈 파일
# 모듈 파일!
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실행 파일
# 실행 파일!
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.mSort(rNums)}')
print(f'sorted rNums DESC: {sm.mSort(rNums, asc=False)}')결괏값:
not sorted rNums: [4, 72, 58, 13, 83, 30, 62, 92, 50, 47]
sorted rNums ASC: [4, 13, 30, 47, 50, 58, 62, 72, 83, 92]
sorted rNums DESC: [92, 83, 72, 62, 58, 50, 47, 30, 13, 4]퀵정렬
퀵정렬이란?
기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
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]퀵정렬(실습)
실습
1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자.
모듈 파일
# 모듈 파일!
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)
else:
return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums)실행 파일
# 실행 파일!
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)}')결괏값:
not sorted rNums: [87, 31, 6, 28, 75, 56, 62, 25, 86, 49]
sorted rNums ASC: [6, 25, 28, 31, 49, 56, 62, 75, 86, 87]
sorted rNums DESC: [87, 86, 75, 62, 56, 6, 25, 28, 31, 49]