DFS를 이해하기 위한 선행으로 Stack과 Queue를 정리했다

DFS를 이해해 보자.

백준 실버로 넘어가며 문제에 접근하기 위해 먼저 유형부터 파악해야 하는 지경에 이르렀다ㅠ

DFS를 알아보기 전에 스택과 큐를 알아야 한다고 하여 정리해 봤다.

 

DFS, BFS는 탐색이라고 한다.

 

 

스택

스택은 선입후출(first in first out)이다. 컵에 담는다고 연상하면 이해하기 쉽다 ㅎㅎ

한쪽 면이 막힌  컵에 데이터를 담으면 처음에 넣는 순서대로 쌓이고

밖으로 꺼낼 때는 거꾸로 마지막에 넣은 데이터부터 꺼내진다.

 

 

파이썬에서 스택을 이용할 때 .append와 .pop 함수는 O(1)이기 때문에 내장된 함수를 바로 사용한다.

append 함수는 오른쪽부터 인덱스를 추가하고

pop 함수는 오른쪽부터 인덱스를 삭제한다.

list = [] # 리스트 선언

list.append(1) # 인덱스 삽입
list.append(2)
list.append(3)
list.pop() # 인덱스 삭제

print(list[::-1]) # 거꾸로 출력 (후입선출)
# 결과
# 1
# 2

print(list) # 선입후출
# 결과
# 2
# 1

 

 

큐

스택은 컵이었고 큐는 양쪽이 뚫려있는 터널에 데이터를 넣는다고 이해한다.

대기열이라고도 많이 설명하는데

먼저 들어온 사람부터 처리하고 보낸다고 이해했다..ㅎ

 

 

 

 

 

큐 용어
Enqueue : 큐 right end에 데이터 추가
Dequeue : 큐 left end에 데이터 삭제

 

 

큐를 쓰려면 덱 라이브러리를 불러와서 사용한다.

스택처럼 리스트를 통해서 큐를 사용할 수도 있지만 시간복잡도가 넘 높아서 비효율적이어서 덱 라이브러리를 사용한다..

라이브러리를 사용하지 않으면 시간복잡도가 O(n)이고 덱을 이용하면 시간 복잡도가 O(1)이다.

 

관행적으로 .append()로 오른쪽부터 인덱스를 추가하고

.popleft()를 사용해서 왼쪽부터 인덱스를 삭제한다.

 

역순으로 출력하려면 reverse함수를 써서 인덱스들을 역순으로 바꾸고 출력한다.

 

from collections import deque # 덱 라이브러리 불러오기

queue = deque() # 큐 선언


queue.append(1) # 오른쪽부터 인덱스 삽입
queue.append(2)
queue.popleft() # 오른쪽부터 인덱스 삭제
queue.append(3)


print(queue)
# 결과
# 1
# 2


# 역순으로 출력하기 위한 로직
queue.reverse()
print(queue)
# 결과
# 2
# 1

 

 

시간복잡도를 고려하면 리스트를 이용하는 것보다 덱을 사용하는 것이 효율적이라고 한다.