20210625 Algorithm 02 : 공간 복잡도, 재귀용법(Recursive call), 재귀 패턴, 재귀용법 활용한 예제(리스트합, 회문, 홀짝, 123표현)

Algorithm 02

공간 복잡도

• 시간 복잡도 : 얼마나 빠르게 실행 되는지

• 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지

  • 실행시간이 짧고, 공간도 적게쓰는 알고리즘이 좋은 알고리즘

• 둘다 만족시키기는 어려움

  • 완전하진 않지만, 시간과 공간은 반비례적 경향이 있음
  • 최근에는 대용량 시스템이 보편화 되면서, 시간복잡도를 우선시킴

• 공간 복잡도 대략적인 계산 필요함
  • 기존 알고리즘 문제는 공간 복잡도 고려해서 만들어진 경우가 많아 시간 + 공간 복잡도에 대한 제약 사항이 있음

공간 복잡도

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련 있는 공간) : 실행 중 동적으로 필요한 공간
  • 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛)
    • c : 고정 공간으로 상수에 해당
    • 𝑆𝑝(𝑛) : 가변 공간으로 공간 복잡도에 주요 영향을 미침

공간 복잡도 계산

• 알고리즘에서 실제 사용되는 저장 공간을 계산하여 빅오 표기법으로 표현하면 됨

예제01 : 팩토리얼 구하기

• n! = 123...n
• n의 값과 상관 없이 변수는 n, fac, index 3개 뿐임
• 공간 복잡도 O(1)

# 사용된 변수 : n, fac, index -> 3개, 입력에 따라서 변수가 늘어 나진 않음
def factorial(n):
  fac = 1
  for index in range(2, n + 1):
    fac = fac * index
  return fac
factorial(3) # 6

예제02 : 팩토리얼 구하기(재귀 함수 방법)

• n! = 123...n
• 재귀함수를 사용하였기 때문에, n에 따라서 함수가 계속 실행 됨으로서 변수 n 이 n개가 만들어짐
• n 부터 1까지 스택이 쌓임
• 공간 복잡도 O(n)

# 계속 함수에서 함수를 불러 오면서 n 이라는 변수가 계속 생겨나서 n번 생겨남
def factorial(n):
  if n > 1:
    return n * factorial(n - 1)
  else:
    return 1

재귀 용법(Recursive call, 재귀 호출)

• 고급 정렬 알고리즘에서 재귀 용법을 사용

재귀 용법 (recursive call, 재귀 호출)

• 쉬운 알고리즘의 경우 많이 사용함
• 함수 안에서 동일한 함수를 호출 하는 형태

예제01: 팩토리얼

• 경우 분석
  • 2! = 1 * 2
  • 3! = 1 _ 2 _ 3
  • 4! = 1 _ 2 _ 3 _ 4 => 4 _ 3!

• 규칙 찾기 : n! = n * (n-1)!
  • n! 부분과 (n-1)! 부분이 안에 들어간 변수만 다르고 비슷함
    • n! = n _ (n-1)! -> n _ (n-1) * (n-2)!
    • 팩토리얼 모양을 계속 전개가 가능함 -> 전개하는 로직을 함수로 만들어 재사용
  • 함수를 하나 만든다 -> 함수n은 n>1 이면 return n * 함수(n-1)

• 코드로 적어 보기

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

# 예시
# factorial(num) = num * num-1 * num-2 * ... 2 * factorial(1)

# TEST
for num range(10):
  print(factorial(num))
# 0 1 2 6 24 120 720 5040 40320 362880

• 시간, 공간 복잡도
  • n-1번 반복문을 호출함
  • 함수 호출 할때 마다, 지역변수 n이 n-1개 생성됨
  • 시간, 공간 복잡도 모두 O(n)

재귀 호출의 일반적인 패턴

• 일반적인 형태 01

def function(입력):
  if 입력 > 입력값: # 입력이 일정값 이상이면
    return function(입력 - 1 ) # 입력보다 작은 값으로 자신을 부름
  else:
    return 일정값,입력값, 또는 특정값 # 재귀 호출 종료

• 일반적인 형태 02

def function(입력):
  if 입력 <= 입력값: # 입력이 일정값 이하이면
    return 일정값,입력값, 또는 특정값 # 재귀 호출 종료
  function(입력보다 작은 값이 될수 있게) # 입력보다 작은 값으로 자신을 부름
  return 결과값

• 팩토리얼 예제 형태 02로 표현하기

def factorial(num):
  if num <= 1:
    return num
  return_value = num * factorial(num - 1)
  return return_value

재귀용법과 Stack 구조

• reculsiv (재귀용법)은 전형적인 Stack 자료 구조의 형태로 관리됨
• python에서는 재귀함수 깊이가 한번 호출에 1000회 이하가 되어야 함 (stack 공간을 제한해 두었음)

재귀 용법을 활용한 프로그래밍 연습

예제01 : 1부터 num 까지의 곱이 출력되게 만들기

# 반복문을 사용한 방법
def multiple(num):
  return_value = 1
  for index in range(1, num + 1):
    return_value = return_value * index
  return return_value

# 재귀 함수를 사용한 방법
def multiple(num):
  if num <= 1:
    return num
  return num * multiple(num - 1)

예제02 : 숫자가 들어 있는 리스트, 리스트의 합을 리턴하는 함수

# 랜덤 list 만들기
import random
data = random.sample(range(100), 10)
print(data) # [50, 76, 39, 55, 6, 20, 37, 17, 5, 23]

# 반복문 사용
def sum(data):
  return_value = 0
  for index in data:
   return_value += index
  return return_value

# 재귀함수 사용
# python의 slicing을 사용(슬라이싱의 경우 값을 가져와 사용하기만 하기 때문에 원본 지장이 없음)
def sum_list(data):
  if len(data) > 1:
    return data[0] + sum_list(data[1:])
  else:
    return data[0]

# pop 사용 (단점: 변수 2개 사용, 원본에 지장을 줌)
def sum_list(data):
  if len(data) > 1:
    num = data.pop(1)
    return num + sum_list(data)
  else:
    return data[0]

• 참고) Python의 리스트 슬라이싱 :

string = 'Dave'
print(string[-1]) # e
print(string[0]) # D
print(string[1:-1]) # av
print(string[:-1]) # Dav

예제03 : 회문 판별 함수

• 회문(palindrome) : 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미

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

# and로 축약
def palindrome(data):
  if len(data) <= 1:
    return True
  return (data[0] == data[-1]) and palindrome(data[1:-1])

예제04 : 홀짝

• 정수 n이 홀수 -> n = 3 * n + 1
• 정수 n이 짝수 -> n = n / 2
• n이 1이 될때 까지 반복

# 반복문
def func(n):
while n == 1:
  print(n)
  if n % 2 == 1:
    n = 3 * n + 1
  else:
    n = n / 2
return n

# 재귀함수
def func(n):
print(int(n))
if n == 1:
  return n

if n % 2 == 1:
  return func(3 * n + 1)
else:
  return func(n / 2)

예제05 : 정수n을 1, 2, 3 의 합으로 표현하는 경우의 수

• 예) 정수 4를 1, 2, 3으로 표현 가짓수 -> 7가지
  • 1+1+1+1
  • 2+1+1, 1+2+1, 1+1+2
  • 2+2
  • 3+1, 1+3

• 패턴찾기

  • f(1) => 1개

    • 1

  • f(2) => 2개

    • 1+1, 2

  • f(3) => 4개

    • 1+1+1
    • 1+2, 2+1
    • 3

  • f(4) => 7개

    • 1+1+1+1
    • 2+1+1, 1+2+1, 1+1+2
    • 2+2
    • 3+1, 1+3

  • f(5) => 13개

    • 1+1+1+1+1
    • 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2
    • 2+2+1, 2+1+2, 1+2+2
    • 3+1+1, 1+3+1, 1+1+3
    • 3+2, 2+3

  • f(6) => 13개

    • 1+1+1+1+1+1
    • 2+1+1+1+1, 1+2+1+1+1, 1+1+2+1+1, 1+1+1+2+1, 1+1+1+1+2
    • 2+2+1+1, 2+1+2+1, 1+2+2+1, 1+1+2+2, 1+2+1+2, 2+1+1+2
    • 2+2+2
    • 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3
    • 3+2+1, 3+1+2, 2+1+3, 2+3+1, 1+2+3, 1+3+2
    • 3+3

• f(4) = f(1) + f(2) + f(3)
• f(5) = f(2) + f(3) + f(4)
• f(6) = f(3) + f(4) + f(5)
• f(n) = f(n-3) + f(n-2) + f(n-1)

def func(data):
  if data == 1:
    return 1
  elif data == 2:
    return 2
  elif data == 3:
    return 4
  return  func(data - 1) + func(data - 2) + func(data - 3)