[제로베이스] 4주차_알고리즘 04

📌2/22 영상강의 6_025 ~ 6_030 복습

🖥️하노이의 탑

           # 원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):                    
    if discCnt == 1:
        print(f'{discCnt}disc: {fromBar}에서 {toBar}(으)로 이동!')

    else:
          # (discNo-1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viaBar, toBar)  
        
          # discNo를 목적 기둥으로 이동
        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:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx],asc=asc)
    rightNUms = mSort(ns[midIdx:len(ns)],asc=asc)



    leftIdx = 0; rightIdx = 0
    mergeNums = []

    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:]      mergeNums에 차례대로 추가하고 남는 마지막수는
                                                      가장 큰 값이자 비교대상이 없어 남아 있게 되므로 
                                                      mergeNums 뒤에 붙여 주도록 한다
    return mergeNums
    
    
    
#호출부
import random as rd
import sortMod as sm

rNum = rd.sample(range(1,101),10)
print(f'not sorted rNum : {rNum}')


print(f'sortd rNum ASC: {sm.mSort(rNum)}')
print(f'sortd rNum DESC: {sm.mSort(rNum,asc=False)}')

• 오름차순 내림차순을 선택옵션으로 넣을때 재귀함수 부분에 asc=asc를 넣어준다. 인수에서 던진 asc = True/False 옵션이 재귀함수 돌릴때도 똑같이 적용될수 있도록!

🖥️퀵정렬 실습

#모듈
def qSort(ns,asc = True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    leftNums = []; midNums = []; rightNums = []
    if asc:
        for n in ns:
            if n < midVal:
                leftNums.append(n)

            elif n == midVal:
                midNums.append(n)

            else:
                rightNums.append(n)
    else:
        for n in ns:
            if n > midVal:
                leftNums.append(n)

            elif n == midVal:
                midNums.append(n)

            else:
                rightNums.append(n)

    return qSort(leftNums,asc=asc) + midNums + qSort(rightNums,asc=asc)
    
#호출부
import random as rd
import sortMod as sm

rNums = rd.sample(range(1,101),10)

print(f'not sored rnums:{rNums}')
print(f'sored rnums ASC:{sm.qSort(rNums)}')
print(f'sored rnums DESC:{sm.qSort(rNums,asc=False)}')

마무리
문제풀이 부분은 다음 노트에 모아서 적어야지
하노이는..다시 봐도 모르겠고! 내일 또 봐야겠다. 코테에 있던데..이해해서 풀고싶다
병합 정렬, 퀵 정렬 코드 짜는 정도가 지금 내 실력인거같은데 지금 괜찮은건가? 하다보면 되는건가?
움... 모르겠고 그냥 하자