스택, 큐 그리고 재귀함수 (2021/02/20)

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 탐색알고리즘으로는 DFS와 BFS가 있는데 이 둘을 이해하기 위해선 기본적인 자료구조인 스택과 큐를 이해해야한다.

 

삽입 - push

삭제 - pop

 

오버플로 - 가득 찬 상태에서 삽입하는 경우

언더플로 - 비어있는 상태에서 삭제하는 경우

 

 

스택

 

스택은 박스쌓기에 비유할 수 있다. 선입후출 또는 후입선출로 이야기하며 

 

파이썬에서

 

stack=[]

stack.append(3)
stack.append(2)
stack.pop()
stack.append(1)

print(stack)

 

결과로는 [3, 1]을 얻을 수 있다.

 

 

큐

 

큐는 대기줄에 비유할 수 있다. 선입선출이라고 이야기하며

 

파이썬에서 

 

from collections import deque

queue = deque()


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

print(queue)

 

결과로 deque([3, 2, 1])를 얻을 수 있다.

 

스택과 다르게 from collections import deque을 해줘야 하고, 삭제를 pop이 아닌 popleft로 표현한다.

 

collections 모듈에서 제공하는 deque 자료구조를 사용한다는 차이점이있다.

 

 

재귀함수

 

재귀함수는 자기 자신을 다시 호출하는 함수를 말한다.

 

단순히 파이썬에서 재귀함수를 표현하면

 

def recursive():
    recursive()
    
recursive()

재귀의 최대 깊이를 초과했다는 오류가 뜬다.

 

재귀함수를 사용할 때는 꼭 종료조건을 명시해야한다.  

 

일반적으로 재귀함수를 사용하는 경우 반복문으로 똑같이 표현할 수 있고 그 반대도 같다.