Python algorithm 개념 및 실습 - 피보나치, 하노이 탑

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

 

피보나치 수열 : 바로 앞 두 수를 더한 값을 다음 값으로 계속 더 한 값

ex )  0,1,1,2,3,5,8,13,....

def fib(n):

    if n <= 1:

        return n

    else:

        return fib(n - 2) + fib(n - 1)

if __name__ == "__main__":

    print(fib(2))  # 0번값 + 1번값

    print(fib(3))

    print(fib(7))  # 5번값 + 6번값

 

 

하노이 탑 

• 입력값 : 움직이려고 하는 원반 개수
• 출력값 : 원반을 옮기는 순서
•  from_pos : 출발점 기둥
•  to_pos : 도착점 기둥
• aux_pos : 보조 기둥

하노이의 탑 옮기기

• 원반이 n 개 일 때
  • `1번 기둥에 있는 n 개 원반 중 n-1개를 2번 기둥으로 옮기기(3번기둥 보조기둥)
  • 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮기기
  • 2번 기둥에 있는 n-1 개 우너반을 다시 3번 기둥으로 옮기기(1번 기둥 보조기둥)

def hanoi(n, from_pos, to_pos, aux_pos):

    if n == 1:

        print(from_pos, "===>", to_pos)

        return

    # 원반 n-1 개를 보조 기둥으로 움직이기

    hanoi(n - 1, from_pos, aux_pos, to_pos)

    # 가장 큰 원반을 목적지로 이동

    print(from_pos, "===>", to_pos)

    # 보조기둥에 있는 원반 n-1개를 목적지로 이동

    hanoi(n - 1, aux_pos, to_pos, from_pos)

if __name__ == "__main__":

    print("n = 1(원반 1개)")

    hanoi(1, 1, 3, 2)

    print()

    print("n = 2(원반 2개)")

    hanoi(2, 1, 3, 2)

    print()

    print("n = 3(원반 3개)")

    hanoi(3, 1, 3, 2)