DFS, BFS 공부 전에 알아야 할 것

DFS, BFS 공부 전에 알아야 할 것

 

Stack 자료구조

• 입구와 출구가 동일한 형태로, 선입후출 자료구조.
• Python에서는 다른 표준 라이브러리를 이용할 필요 없이 리스트 자료형을 이용하여 스택을 구현한다.
• 가장 오른쪽에 자료를 산입하는 append()와 가장 오른쪽에서 하나의 원소를 꺼내는 pop()를 지원하는데, 이를 그대로 이용해서 스택과 같이 사용할 수 있다.
• 나중에 모든 작업이 끝난 후 스택을 출력할 땐, 최상단 원소부터 출력하려면 [::-1]을 통해 출력해야한다.

---

Queue 자료구조

• 선입선출의 자료구조, 차례대로 작업을 시행하는 대기열을 나타내고자 할 때 사용.
• 큐 자료구조를 Python에서 이용하고자 할 땐 deque(덱) 라이브러리를 사용하면 된다.
• Stack과 같이 리스트 자료형으로 구현할 순 있지만 시간복잡도가 높아 비효율적이기 때문에 deque을 사용.
• 자료를 삽입하려면 append() 삭제할 땐 popleft()를 사용하면 된다.
• 만약 pop()을 호출하게되면 원소를 꺼낸 후에 원소의 위치를 조정하는 과정을 한 번 더 거쳐야 하기 때문에 시간복잡도가 늘어난다.
• append()를 사용하여 오른쪽에서 삽입되고, 왼쪽에서 나가야하기 대문에 popleft()!
• 따라서 먼저 들어온 순서대로 출력하려면 print(queue)를 해주면 되고 역순으로 출력하려면 queue.reverse()가 필요하다.

 

---