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)하노이의 탑

 

팩토리얼 :  4! = 4 * 3 * 2 * 1

 

def fact(n):

    result = 1

    # range사용하면 마지막 번호를 사용하지 않는데 사용해야하기 때문에 +1

    for i in range(1, n + 1):

        result = result * i

    return result

if __name__ == "__main__":

    print("3! = ", fact(3))

    print("5! = ", fact(5))

    print("10! = ", fact(10))

 

 

 

재귀 호출 : 어떤 함수에서 자기 자신을 부르는 것

• 기본 단계 : 자기 자신을 호출하지 않는 부분(무한 반복 방지)
• 재귀 단계 : 자기 자신을 다시 호출하는 부분
• 반복하는 부분이 있다면 끝나는 부분을 반드시 명시

 

 

# 잘못된 예제

def hello():

    print("hello")

    hello()

hello()

# RecursionError: maximum recursion depth exceeded while calling a Python object : 계속 호출을 많이해서 메모리에 부담되니 종료.

 

팩토리얼 재귀호출 방식으로

# 팩토리얼

def fact(n):

    # 기본 단계 - 끝내는 부분

    if n == 1:

        return 1

    # 반복단계

    else:

        return n * fact(n - 1)

if __name__ == "__main__":

    print("3! = ", fact(3))

    print("5! = ", fact(5))

    print("10! = ", fact(10))

   

 

 

 

# n까지의 합

def rec_sum(n):

    if n == 1:

        return 1

    else:

        return n + rec_sum(n - 1)  # n * (n + 1) // 2

if __name__ == "__main__":

    print("3까지의 합 = ", rec_sum(3))

    print("5까지의 합 = ", rec_sum(5))

    print("10까지의 합 = ", rec_sum(10))