<3주차_2일> 알고리즘(2)

가장 까다로운 재귀 알고리즘에 대하여 공부하였다.

• 재귀 알고리즘 : 나 자신을 다시 호출하는 것을 재귀라고 한다.

• 팩토리얼

	def factorial(num):
		if num > 0:
    		return num * factorial(num - 1)
    	else:
    		return 1

• 유클리드 호제법

	def Euclidean(n1, n2)
    	r = n1 % n2
		#나머지가 0이면 n2가 최대 공약수.
    	if n1 % n2 == 0:
        	return n2

    	return uclid(n2, r)

• 하노이의 탑 : 세개의 기둥을 이용해서 크기가 다른 원판을 다른 기둥으로 옮기는 게임. 한 번에 한 개의 원판만 옮길 수 있고, 큰 원판이 작은 원판 위에 있어서는 안된다.

	            #원판 갯수, 현재 기둥, 최종 기둥, 중간기둥
	def moveDist(discCnt, fromBar, toBar, viaBar):
	    if discCnt == 1:
	        print(f'{discCnt}disc : {fromBar}에서 {toBar}(으)로 이동!')
	    else:
	        moveDist(discCnt-1, fromBar, viaBar, toBar)
	        print(f'{discCnt}disc : {fromBar}에서 {toBar}(으)로 이동!')
	        moveDist(discCnt-1, viaBar, toBar, fromBar)

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

	def mSort(ns, asc=True):

    	if len(ns) < 2:
	        return ns
		
        #양쪽으로 분할해서 정렬.
	    midIndx = len(ns) // 2
	    leftNums = mSort(ns[0:midIndx], asc=asc)
	    rightNums = mSort(ns[midIndx:len(ns)], asc=asc)
		
        # 분할한 리스트 정렬 후 병합.
	    mergeNums = []
	    leftIndx = 0; rightIndx = 0
	    while leftIndx < len(leftNums) and rightIndx < len(rightNums):

	        if asc:
	            if leftNums[leftIndx] < rightNums[rightIndx]:
               	 	mergeNums.append(leftNums[leftIndx])
	                leftIndx += 1
	            else:
               	 	mergeNums.append(rightNums[rightIndx])
	                rightIndx += 1
	        else:
	            if leftNums[leftIndx] > rightNums[rightIndx]:
               	 	mergeNums.append(leftNums[leftIndx])
	                leftIndx += 1
	            else:
               	 	mergeNums.append(rightNums[rightIndx])
	                rightIndx += 1
         
         # 정렬하지 않은 나머지를 끝에 붙여둔다.           
	    if leftIndx < len(leftNums):
	        mergeNums = mergeNums + leftNums[leftIndx:]
	    else:
	        mergeNums = mergeNums + rightNums[rightIndx:]
	    
        return mergeNums

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

	def qSort(ns):

	    if len(ns) < 2:
	        return ns
	    else:
        	#기준값을 정하고 작고 크고 같은 값들을 따로 정한다.
	        midIndx = len(ns)//2
	        mid = []
	        left = []
	        right = []

	        for n1 in ns:
	            if n1 < ns[midIndx]:
	                left.append(n1)
	            elif n1 == ns[midIndx]:
	                mid.append(n1)
	            else:
	                right.append(n1)
                    
			# 각 부분을 다시 퀵정렬 후 병합한다.
	        left = qSort(left)
	        right = qSort(right)
	        merge = left + mid + right

	        return merge