스택, 큐, 재귀함수

알고리즘 파트는 책 "이것이 취업을 위한 코딩테스트다 -나동빈" 책을 기반으로 제가 이해한부분을 정리하기 위해 작성되었습니다 .

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 이 둘을 이해하기에 앞서 먼저 알아야 할 기보 자료구조부터 알아보자. (자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조)

- 삽입 : push

- 삭제 : pop

- Overflow : 특정 자료구조가 수용할 수 있는 데이터 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때

- Underflow : 특정 자료구조에 데이터가 전혀 들어있지 않는데 삭제 연산을 수행할 때

 

스택 (Stack)

- FILO : First In Last Out (선입후출) 먼저 입력되는 데이터가 나중에 출력된다.

stack = []
stack.append(5)
stack.append(3)
stack.append(2)
stack.pop()
stack.append(7)
stack.append(8)
stack.pop()

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

# [5,3,7]
# [7,3,5]

- 스택의 시간복잡도 : O(1)

---

큐 (Queue)

- FIFO : First In First Out (선입선출) 일반적인 대기줄과 같이 먼저 입력된 데이터가 먼저 출력된다.

- 파이썬에서는 collections 모듈에서 제공하는 deque 자료구조를 활용하는 것이 좋다. 테이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue라이브러리를 이용하는 것보다 간단하다.

- deque 객체를 list로 반환하기 위해선 list(queue) 사용하면 된다.

from collections import deque

queue = deque()

queue.append(5)
queue.append(3)
queue.append(2)
queue.popleft()
queue.append(7)
queue.append(8)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

# [2,7,8]
# [8,7,2]

- 시간복잡도 : O(1)

---

재귀함수 (Recursive Function)

재귀함수란 자기 자신을 다시 호출하는 함수이다. 어느 정도 출력하게 되면 다음의 오류 메시지를 출력한다.

RecursiveError : maximum recursion depth exceeded while pickling an object

이 말은 재귀의 최대 깊이를 초과했다는 내용이다. 파이썬 인터프리터의 호출 횟수 제한을 벗어나서 발생하는 오류다. 그렇기 때문에 종료 조건을 반드시 명시해야 한다! 컴퓨터 내부에서 재귀함수는 스택 자료구조를 이용한다. 그렇기 때문에 스택 자료구조를 이용해야 하는 알고리즘에서는 재귀함수를 이용하면 간편하게 구현이 가능하다. DFS가 대표적 예다.

 

반복문 대신 재귀함수를 사용했을 때의 장점은 뭐가 있을까?

- 점화식(특정 함수를 자신보다 작은 변수에 대한 함수와의 관계로 표현한 것)을 이용해 간결해진 소스코드