자료구조와 알고리즘 학습 노트 기초 (2) 재귀와 귀납적 사고

복습

추상 데이터타입 (ADT : Abstract Data Type)

데이터나 연산이 무엇인가는 정의되지만 데이터나 연산을 컴퓨터 상에서 어떻게 구현하는가는 정의되지 않는다

 

재귀

(순환)

알고리즘이나 함수가 수행 도중 자기 자신을 다시 호출하여 문제를 해결하는 기법

* Good 정렬, 탐색

* Bad 피보나치수, 최적 행렬곱 경로

 

ex. 팩토리얼의 정의 (n!)

 

def factorial(n):
    if n<=1: return 1
    else : return (n*factorial(n-1))
    
print(factorial(3))

 

factorial (5) = 5 * factorial (4) -> = 5 * 4 * factorial (3) -> ...... -> = 5 * 4 * 3 * 2 * 1 = 120

 

재귀호출의 가장 중요한 것은 재귀 호출을 멈추는 부분이 있어야한다

만약 없다면? 무한호출

 

순환 vs 반복

시간 복잡도가 동일할 때 어떤 것이 더 효율적인가?

바로 공간의 차이

 

프로그램의 중요도

1. Success rate 

2. time

3. memory

 

 

거듭제곱 반복 O(n) vs 재귀 O(lon_2 n)

 

 

 

 

피보나치 반복적인함수 O(n) 

 

 

하노이의 탑

def move(n, a, b, c):
    if n > 0:
        move(n-1, a, c, b)
        print(f"{a}에 있는 원반을 {b}로 옮긴다.")
        move(n-1, c, b, a)


def main():
    print(move(4, 1, 2, 3))


if __name__ == '__main__':
    main()