[이코테 2021] 4. 스택, 큐, 재귀함수

🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.

스택 자료구조

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

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

[실행 결과]

[1,3,2,5]
[5,2,3,1]

• append() 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼낸다.

큐 자료구조

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

from collections import deque

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

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

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

[실행 결과]

deque([3,7,1,4])
deque([4,1,7,3])

• 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자.
  deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.
• 구현상으로 실제 데이터가 오른쪽으로 들어와서 왼쪽으로 나간다.

재귀 함수

• 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.
• 단순한 형태의 재귀함수 예제

# '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다.
def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()

recursive_function()

여기서 정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다.

• 하지만 어느 정도 출력하다가 다음과 같은 오류 메시지를 출력하고 멈출 것이다.
  RecursionError: maximum recursion depth exceeded while pickling an object
→ 이 오류 메시지는 재귀의 최대 깊이를 초과했다는 내용이다. 따라서 무한대로 재귀 호출을 진행할 수는 없다.

재귀 함수의 종료 조건

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

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

recursive_function(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):
	if n<=1:  # n이 1 이하인 경우 1을 반환
    	return 1
    # n! = n*(n-1)!를 그대로 코드로 작성하기
    return n*factorial_recursive(n-1)

# 각각의 방식으로 구현한 n! 출력(n=5)
print('반복적으로 구현: ', factorial_iterative(5))
print('재귀적으로 구현: ', factorial_recursive(5))

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

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다.

• 유클리드 호제법
  두 자연수 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)

print(gcd(192,162))

[실행 결과]

6

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