[자료구조] 스택, 큐, 재귀함수 / Python 파이썬

 

이번 포스트에서는 스택, 큐, 재귀함수에 대해 살펴볼 예정이다.

 

---

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 

ex) 박스 쌓기, 프링글스 통 구조

 

(LIFO) 마지막에 있는 데이터가 먼저 처리된다.

 

스택구조를 이용하는 것은 단순한 리스트 삽입구조를 이용하면된다. (시간 복잡도 O(1), 상수시간)

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

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

이미지 출처: awesomeo184.log

---

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.
• 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화할 수 있다.

(FIFO)차례대로 먼저 들어온 데이터가 먼저 처리된다.

큐의 기본 연산

파이썬의 리스트를 이용하면 큐는 기본적으로 다음과 같은 연산들이 필요하다.

Q.enqueue(e): back에 요소 e를 추가
Q.dequeue(): front의 요소를 반환하면서 제거
Q.first(): front의 요소를 제거하지 않고 반환
Q.is_empty(): 큐가 비어있으면 True를 반환

 

 

 

큐 구조를 이용하는 것은 deque 라이브러리를 이용한다. (시간 복잡도 O(1), 상수시간)

리스트로 구조 적으로는 큐를 구현할 수 있지만 시간복잡도가 길어진다는 단점이 있다.

from collections import deque

# 큐 구현을 위해 deque 라이브러리 사용
queue = deque() 

queue.append(n) #원소를 넣을 때
queue.popleft(n) #원소를 뺄 때

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾸기
print(queue) #나중에 들어온 워소부터 출력

 

 

---

재귀 함수

• 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.
• 단순한 형태의 재귀함수 예재
  • '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력합니다.
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.

def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

 

 

재귀 함수가 계속 출력된 창

*코딩테스트에는 일반적으로 재귀함수를 이용해도 통과할 수 있다.

재귀 함수를 통해 while이나 for문을 이용하지 않아도 반복문을 이용할 수 있다.

스택 프레임과 비슷하다. (선입 후출)

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야한다.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.

* 종료 조건을 포함한 재귀 함수 예제

def recursive_function(i):
	# 종료조건을 명시
	if i == 100: 
    	return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.') 
    recursive_function(i + 1) 
    print(i, '번째 재귀함수를 종료합니다.')
    
recursive_function(1)

---

재귀함수 구현 예제

팩토리얼 구현 

• n! = 1 * 2 * 3 * ''' * (n-1) * n
• 수학적으로 0!과 1!의 값은 1이다.

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
        result *= i
    
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    # n이 1 이하인 경우 1을 반환    
    if n <=1:
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성
    return n * factorial_recursive(n-1)

 

최대공약수 계산 (유클리드 호제법) 예제

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다.
• 유클리드 호제법
  • 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자.
  • 이 때 A와 B의 최대 공약수는 B와R의 최대공약수와 같다.
• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있다.

 

1단계: A = 192 ,B = 162 

R = A % B = 30

# 이 때 나머지 값(R)을 구하고 나면 2단계에서 A,B = B,R 로 스왑된다.

 

2단계: A = 162 (1단계의 B값), B = 30 (1단계의 R값)

 

R = A % B = 12

 

3단계: A = 30 (2단계의 B값), B = 12 (2단계의 R값)

 

R = A % B = 6

 

4단계: A = 12 (2단계의 B값), B = 6 (2단계의 R값)

 

R = A % B = 0

 

나머지가 0이므로 따라서 6이 최대공약수가 된다.

 

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

 

재귀함수 사용의 유의 사항

 

• 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다
• 모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있다
• 재귀 함수가 반복문 보다 유리할 수도, 불리할 수도 있다
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터메모리 내부의 스택 프레임에 쌓이게 된다
  • 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다

 

 

 

 

 

---

References

- 알음알음 성장로그

  https://hei-jayden.tistory.com/35

- awesomeo184.log

  https://velog.io/@awesomeo184/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90Queue