그래프 탐색 알고리즘: DFS / BFS
- 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
- 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.
- DFS와 BFS 는 코딩테스트에서 매우 자주 등장하는 유형이다
이를 위해 알아야 할 자료구조, 스택과 큐
스택 자료구조
- 먼저 들어온 데이터가 나중에 나가는 형태. (상자 쌓기)
- 입구와 출구가 동일한 형태
- 삽입 / 삭제 로 동작
파이썬에서 스택 자료구조를 이용하기 위해서는 단순히 리스트를 사용하면 된다. 리스트 자료형은 가장 오른쪽에 데이터를 집어넣는 append()메소드와 가장 오른쪽에서 데이터를 제거하는 pop()메소드를 지원하기 때문에 이를 그대로 이용하여 스택과 같이 사용할 수 있다. 또한 append() 함수와 pop()함수의 시간복잡도는 상수시간 즉 O(1) 이기 때문에 파이썬에서는 별도로 다른 표준 라이브러리 필요 없이 기본적으로 제공되는 객체인 리스트를 이용하여 스택 자료구조를 사용할 수 있다.
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
print(stack) # [5,2,3,7]
stack.pop()
print(stack) # [5,2,3]
stack.append(8) #[5,2,3,8]
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
큐 자료구조
- 먼저 들어온 데이터가 먼저 나가는 자료구조 (영화관 줄서기)
큐 자료구조를 파이썬에서 이용하고자 할 때는, deque 라이브러리를 사용한다. 사실, 단순히 리스트 자료형을 이용하여 큐를 구현할 수도 있으나, 시간 복잡도가 높아서(당연) 비효율적으로 동작하기에, 파이썬에서 큐 자료구조를 이용하고자할 때는 반드시 deque 라이브러리를 활용한다. 덱을 이용하는 것이 리스트를 이용하는 것보다 시간적으로 우수하다!
파이썬에서 특정 인덱스의 원소를 꺼내기 위해 리스트의 pop 메서드를 호출한다면, 원소를 꺼낸 뒤에 원소의 위치들을 재조정하는 과정이 필요하기 때문에 원소를 꺼내는 것 자체가 높은 시간 복잡도가 요구됨. 그렇기에 덱을 이용해 큐를 구현하자.
from collections import deque
queue = deque() # 하나의 deque 객체 생성
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
print(queue) # [5,2,3,7]
queue.popleft()
print(queue) # [2,3,7] 먼저 들어온 원소부터 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # [7,3,2]이상, 스택과 큐 자료구조에 대해 알아보았고, 그것을 어떻게 프로그램 상으로 구현할 수 있는지에 대해 공부했다.
