#41. Algorithm31_python) 스택(Stack), 큐(Que), 재귀 함수(Recursive Function)

DFS, BFS를 이해하기 위해서는 기본 자료구조인 스택과 큐를 이해해야 하고, 재귀 함수를 알아야 한다.

 

 

1. Stack

• Stack는 박스 쌓기에 비유할 수 있음
• 선입후출(First In Last Out) or 후입선출(Last In First Out)
• 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없음
• 기본 리스트에서 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작
• append()메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼냄

출처 : https://velog.io/@mayy24th/%EC%8A%A4%ED%83%9D-stack

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)         # 최하단 원소부터 출력
print(stack[::-1])   # 최상단 원소부터 출력

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

 

2. Que

• Que는 대기 줄에 비유할 수 있음
• 선입선출(First In First Out) : 먼저 들어가면 먼저 나옴

출처 : https://velog.io/@mayy24th/%ED%81%90-queue

from collections import deque

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

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
print(queue)

queue.popleft()
print(queue)

queue.append(1)
queue.append(4)
print(queue)

queue.popleft()
print(queue, end = '\n\n')     # 먼저 들어온 순서대로 출력

queue.reverse()                # 다음 출력을 위해 역순으로 바꾸기
print(queue)                   # 나중에 들어온 원소부터 출력

>>>
deque([])
deque([5, 2, 3, 7])
deque([2, 3, 7])
deque([2, 3, 7, 1, 4])
deque([3, 7, 1, 4])

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

# deque 객체를 리스트 자료형으로 변경
list_from_deque = list(queue)
list_from_deque

>>>
[4, 1, 7, 3]

 

3. 재귀 함수 : Recursive Function

• 자기 자신을 다시 호출하는 함수
• 프랙탈(Fracktal) 구조와 유사

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

recursive_function()

'''
코드 실행하면 문자열이 무한히 출력
'''

•  
• 재귀 함수의 종료 조건
  • 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.
  • 자칫 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있다.

def recursive_function(i):
    # 100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 10:
        return

    print(i,'번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출')
    recursive_function(i+1)
    print(i,'번째 재귀 함수를 종료')

recursive_function(1)

>>>
1 번째 재귀 함수에서 2 번째 재귀 함수를 호출
2 번째 재귀 함수에서 3 번째 재귀 함수를 호출
3 번째 재귀 함수에서 4 번째 재귀 함수를 호출
4 번째 재귀 함수에서 5 번째 재귀 함수를 호출
5 번째 재귀 함수에서 6 번째 재귀 함수를 호출
6 번째 재귀 함수에서 7 번째 재귀 함수를 호출
7 번째 재귀 함수에서 8 번째 재귀 함수를 호출
8 번째 재귀 함수에서 9 번째 재귀 함수를 호출
9 번째 재귀 함수에서 10 번째 재귀 함수를 호출
9 번째 재귀 함수를 종료
8 번째 재귀 함수를 종료
7 번째 재귀 함수를 종료
6 번째 재귀 함수를 종료
5 번째 재귀 함수를 종료
4 번째 재귀 함수를 종료
3 번째 재귀 함수를 종료
2 번째 재귀 함수를 종료
1 번째 재귀 함수를 종료

• 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용
  • 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료
• 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있음
  • DFS가 대표적

 

 

<참조>

• 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어)