탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데, 이 알고리즘은 스택과 큐에 대한 이해가 전제되어야 한다.
따라서 스택과 큐에 대해 알아보자.
자료구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조이다.
스택과 큐는 다음의 개념을 바탕으로 핵심적인 함수로 구성된다.
- 삽입(Push) : 데이터를 삽입한다.
- 삭제 (Pop) : 데이터를 삭제한다.
또한 스택과 큐를 사용할 땐 Overflow와 Underflow도 고민해야한다.
Overflow : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다.
Underflow : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태일 때 발생한다.
Stack
흔히 박스 쌓기에 비유 할 수 있다. 박스를 쌓으려면 가장 아래서 부터 쌓아야 하며 박스를 치울 때는 제일 위에 있는 박스부터 치워야 한다. 이러한 구조를 선입 후출 또는 후입 선출이라고 한다. (FILO/LIFO)
예를 들어 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5) - 삭제 ()
의 과정이 이루진다고 가정해보자. 그렇다면 아래와 같이 전개될 것이다.
- 삽입 (1)
1 - 삽입(1) - 삽입(2)
1 2 - 삽입(1) - 삽입(2) - 삽입(3)
1 2 3 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제()
1 2 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4)
1 2 4 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5)
1 2 4 5 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5) - 삭제 ()
1 2 4
위와 같이 끝에 데이터가 삽입되고 가장 늦게 들어온 숫자 부터 삭제 된다.
파이썬에서 이러한 스택을 사용하려면 별도의 라이브러리 없이 리스트의 append와 pop메서드를 사용하면 된다. append() 메서드는 리스트의 가장 뒤 쪽에 데이터를 삽입 하고 pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.
위의 예시를 파이썬으로 표현하면 다음과 같다.
stack = []
satck.append(1)
satck.append(2)
satck.append(3)
stack.pop()
satck.append(4)
satck.append(5)
satck.pop()Queue
큐는 대기줄에 비유 할 수 있다. 음식을 주문하기 위해 대기줄을 섰다고 가정하자. 그렇다면 가장 먼저 줄을 선 사람이 가장 먼저 음식을 주문할 것이다. 따라서 처음 데이터가 먼저 삭제 되고 삽입은 맨 뒤에서 일어난다.
이러한 구조를 선입선출이라고 한다. (FIFO)
예를 들어 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5) - 삭제 ()
의 과정이 이루진다고 가정해보자. 그렇다면 아래와 같이 전개될 것이다.
- 삽입 (1)
1 - 삽입(1) - 삽입(2)
1 2 - 삽입(1) - 삽입(2) - 삽입(3)
1 2 3 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제()
2 3 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4)
2 3 4 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5)
2 3 4 5 - 삽입(1) - 삽입(2) - 삽입(3) - 삭제() - 삽입(4) - 삽입(5) - 삭제 ()
3 4 5
파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하면 된다.
deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(4)
queue.append(5)
queue.popleft()