AI교육과정 - Python.8

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘, 고급 정렬 알고리즘 작성 시 자주 사용됨

1. 재귀 호출 분석

   • 2! = 1 * 2
   • 3! = 1 2 3
   • 4! = 1 2 3 4 = 4 3!

2. 규칙

   • n! = n * (n-1)!
     • 함수로 만들어 보자
     • 함수(n)은 n=1 이면 return n
     • 함수(n)은 n>1 이면 return n * 함수(n-1)

3. 검증

   • 2!
     • 함수(2)이면 2>1 이므로 2 * 함수(1)
     • 함수(1)은 1이므로 return 2 * 1, 답은 2
   • 3!
     • 함수(3)이면 3>1 이므로 3 * 함수(2)
     • 함수(2)는 위 계산에 의해 2! 이므로 return 2 * 1 = 2
     • 3 함수(2) = 3 2 = 3 2 1, 답은 6
   • 4!
     • 함수(4)이면 4>1 이므로 4 * 함수(3)
     • 함수(3)은 위 계산에 의해 3 2 1 = 6
     • 4 함수(3) = 4 6, 4 3 2 * 1, 답은 24

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

4. 재귀호출의 시간 복잡도

   • factorial(n)은 n-1번의 factorial() 함수를 호출해서 곱셈을 함
     • n-1번 반복문을 호출한 것과 동일
     • factorial() 함수를 호출할 때마다 지역변수 n이 생성됨
     • 시간 복잡도는 O(n-1)이므로 O(n)

5. 재귀호출의 전형적인 예

   • 함수는 내부적으로 스택처럼 관리
   • 코드분석
   • 문제

     1. 회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별하는 함수를 리스트 슬라이싱을 활용하여 만들어보자

        • 재귀함수를 사용
        • 회문이면 True, 아니면 False를 반환

        def palindrome(string):
          if len(string) <= 1:
            return True
          if string[0] == string[-1]:
            return palindrome(string[1:-1])
          else:
            return False

동적 계획법(Dynamic Programming)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분의 값을 활용해서 보다 큰 크기의 부분 문제를 해결함
• 상향식 접근법(최하위 해답을 구한 후, 해당 결과를 이용해서 상위 문제를 풀어가는 방식)
• 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 전체 실행 속도를 빠르게 하는 기술(메모이제이션:Memoization)을 사용
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되기 때문에 재활용

동적 계획법 알고리즘

• 피보나치 수열 n을 입력받아서 아래와 같이 계산
• 피보나치 수열

함수를 '피보나치'라고 한다면
fibonacci(0): 0
fibonacci(1): 1
fibonacci(2): 1
fibonacci(3): 2
fibonacci(4): 3
fibonacci(5): 5
fibonacci(6): 8

1. 재귀호출 사용

   def fibonacci(num):
     if num <= 1:
       return num
     return fibonacci(num-1) + fibonacci(num-2)

2. 동적 계획법 사용

   • 일반적인 동적 계획법 문제는 가장 적은 경우의 수부터 계산해 본 뒤, 패턴을 찾아 식을 세우는 것이 핵심!

   def fibonacci(num):
     cache = [0 for index in range(num+1)]
     print(cache) # [0, 0, 0, 0, 0, 0, 0]
     cache[0] = 0
     cache[1] = 1
   
     for index in range(2, num+1):
       cache[index] = cache[index-1] + cache[index-2]
     return cache[num]

   • 문제 아래 '코딩 테스트' 문제의 답을 작성해보자

     • 문제

       tile = [0 for index in range(1001)]
       tile[1] = 1
       tile[2] = 2
       
       n = int(input())
       
       for index in range(3, 1001):
         tile[index] = tile[index-1] + tile[index-2]
       
       print(tile[n] % 10007)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘
• 하향식 접근법으로 상위의 해당을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식(재귀함수로 구현)
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않음
• Momoization 기법을 사용하지 않음

• 정렬 알고리즘의 꽃(고급 알고리즘)
• 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 모으는 함수를 작성
• 각 왼쪽, 오른쪽은 재귀용법을 사용해 다시 동일 함수로 호출하여 위 작업을 반복함

1. 퀵 정렬 알고리즘 구현

   • 리스트 개수가 1개면 해당 리스트를 리턴
   • 리스트 맨 앞의 데이터를 기준점으로 정함
   • left, right 리스트 변수를 생성
   • 맨 앞에 데이터를 뺀 나머지 데이터를 기준점과 비교
     • 기준점보다 작으면 left에 저장
     • 기준점보다 크면 right에 저장
   • return quicksort(left) + pivot + quicksort(right)로 재귀 호출

   def quicksort(data):
     if len(data) <= 1:
       return data
     pivot = data[0]
     left, right = list(), list()
   
     for index in range(1, len(data)):
       if pivot > data[index]:
         left.append(data[index])
       else:
         right.append(data[index])
     return quicksort(left) + [pivot] + quicksort(right)
   data_list = [11, 85, 45, 50, 33, 68, 14]
   quicksort(data_list) # [11, 14, 33, 45, 50, 68, 85]

2. 퀵 정렬 알고리즘을 list comprehension을 사용하여 더 좋은 알고리즘으로 작성해보기

   def quicksort(data):
     if len(data) <= 1:
       return data
     pivot = data[0]
     left, right = list(), list()
   
     left = [item for item in data[1:] if pivot > item]
     right = [item for item in data[1:] if pivot <= item]
   
     return quicksort(left) + [pivot] + quicksort(right)

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
• 데이터가 담겨있는 리스트르 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

• 최악의 경우 리스트의 길이가 n일 때, n번 비교를 해야함
• 빅오 표기법으로 표현하면 O(n)