자료구조, 재귀함수

스택 자료구조

• First In > Last Out(선입후출)
• 입구와 출구가 동일한 형태(프링글스)

파이썬에서의 스택 예시

stack = []
stack.append()
stack.pop()

print(stack[::-1]) #최상단 원소부터 출력
print(stack) #최하단 원소부터 출력

큐(Queue) 자료구조

• First In > First Out(선입선출)
• 입구와 출구가 뚫려 있음(터널)

파이썬에서의 큐 예시

from collections import deque  #deque 라이브러리 사용

queue = deque()

queue.append()
queue.popleft()

print(queue) 		#먼저 들어온 원소부터 출력
queue.reverse()		#역순으로 변경
print(queue)		#나중에 들어온 원소부터 출력

재귀함수(Recursive Function)

재귀함수: 자기 자신을 다시 호출하는 함수

• 종료 조건 명시하지 않으면 함수가 무한히 호출
• 파이썬은 maximum resursion depth가 있어 무한히 호출되는 것을 중단시킴

def recursive_function():
	print('재귀함수를 호출')
    recursive_function()

recursive_function()

• 종료 조건 포함한 재귀 함수

def recursive_function(i):
	if i == 100:
    	return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료')

recursive_function(i)

재귀함수 예제: 팩토리얼

#반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    for i in range(1, n+1):
    	restult *= i
    return result

#재귀적으로 구현한 n!
def factorial_recursive(n):
	if n<=1:
    	return 1
    return n * factorial_resursive(n-1)

재귀함수 예제: 최대공약수(Greatest Common Divisor)

유클리드 호제법 을 사용

• 두 자연수 A, B에 대하여(이 때 A > B) A를 B로 나눈 나머지는 R이라고 할 때,
• A와 B의 최대공약수는 B와 R의 최대공약수와 같음
  

def gcd(a, b):
	if a % b == 0:
    	return b
    else:
    	return gcd(b, a%b)