재귀, 정렬 알고리즘

하노이탑

def hanoi(n,fr,tmp,to):
    if n == 1: print("원반 1을 %s에서 %s로" %(fr, to))
    else:
    	#n-1개를 시작점에서 임시 지점으로 옮기기
        hanoi(n-1,fr,to,tmp)
        #남은 1개를 목적지로
        print("원판 %d를 %s에서 %s로"%(n,fr,to))
        #임시 지점에 있는 n-1개를 목적지로
        hanoi(n-1,tmp,fr,to)

hanoi(4, 'A', 'B', 'C')

거듭제곱

def pow(x,n):
    if n == 0 : return 1;
    elif n % 2 == 0:
        return pow(x*x, n//2)
    else:
        return x*pow(x*x, (n-1)//2)

print(pow(2,4))
print(pow(2,5))

 

피보나치 순환

def fib(n):
    if n == 1 : return 1
    if n == 0 : return 0
    else: return fib(n-1) + fib(n-2)

print(fib(2))

피보나치 반복

 

def fib(n):
    if (n < 2): return 1

    last = 0
    current = 1
    for i in range(2, n+1):
        tmp = current;
        current += last
        last = tmp

    return current

for i in range(1,11): print(fib(i))

선택

def selection_sort(a):
    for i in range(0,len(a)-1):
        tmp = i
        for j in range(i+1,len(a)):
            if(a[tmp] > a[j]) : tmp = j
        a[i], a[tmp] = a[tmp], a[i]


a = [9999, 11, 22, 677, 3473, 223, 162, 16, 17, 1]

selection_sort(a)
print(a)

삽입

def insertion_sort(a):
    for i in range(1, len(a)): # i는 1번부터 시작
        key = a[i]
        j = i - 1 # j를 루프 외부에서 선언해서 재사용
        #값이 정렬되지 않았으면 한칸씩 뒤로 밀어준다
        while (j >= 0 and a[j] > key):
            a[j+1] = a[j]
            j-=1
        a[j+1] = key

a = [9999, 11, 22, 677, 3473, 223, 162, 16, 1]
insertion_sort(a)
print(a)

버블

def bubble_sort(a):
    for i in range(len(a)):
        bChanged = False; #스왑이 일어나지 않았으면 이미 정렬된거니 반복문을 종료
        #n-i-1, 맨 뒤부터 정렬되니 차례로 인덱스가 줄어든다
        for j in range(0,len(a)-1-i):
            if(a[j] > a[j+1]):
                a[j], a[j+1] = a[j+1], a[j]
                bChanged = True
        
        #최적화를 위해서 더 이상 값 스왑이 일어나지 않으면 반복문 종료
        if bChanged == False: 
            break

a = [9999, 11, 22, 677, 3473, 223, 162, 16, 1]
bubble_sort(a)
print(a)

 

삽입,버블,선택 차이

선택 - 항상 n*n

삽입 - 입력이 정렬된 경우 O(n), 역으로 정렬된 경우 - 최악,O(n*n) 평균 O(n*n)

버블 -  입력이 정렬된 경우 이동횟수 0, 역으로 정렬된 경우 - 최악, 이동횟수 * 3, 평균 O(n*n)

 

정렬 실습문제