알고리즘

7) 제귀 알고리즘(Recusion)

def recusion(num):

    if num > 0:
    	#재귀함수: 자기 자신을 호출
        return num * recusion(num -1)
    else:
        return 1    #0으로 하면 팩토리얼이기 때문에 값이 0 이 된다.

print(recusion(4))

24

실습1. 유클리드 호제법

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

⭐⭐실습2. 하노이의 탑⭐⭐

생각할 점

• 출발기둥, 도착기둥, 경유기둥이 있다.
• 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(으)로 이동!

8) 병합정렬(Merge Sort)

• 
• 

#병합정렬
#자료구조를 분할 하고 각각의 분할 된 자료구조를 정렬한 후 다시 병합하여 정렬한다.

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]

실습1.

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]

9) 퀵 정렬

#퀵정렬
#기준 값 보다 작은 값과 큰 값으로 분리한 후 다시 합친다.

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.

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]