[DFS/BFS 알고리즘] 꼭 필요한 자료구조 기초

자료구조 (Data Structure)

- 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미

- 스택과 큐는 자료구조의 기초 개념으로 Push (삽입)과 Pop (삭제) 두 핵심적인 함수로 구성

 

스택 (Stack)

- 스택은 박스 쌓기에 비유할 수 있음 (흔히 박스는 아래에서부터 위로 차곡차곡 쌓음)

- 이러한 구조를 선입후출 (FILO) 또는 후입선출 (LIFO)라고 함

- 파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없음

- 기본 리스트에서 append(), pop() 함수를 사용하면 스택 자료구조와 동일하게 동작

 

큐 (Queue)

- 큐는 대기줄에 비유할 수 있음 (흔히 놀이공원에서 줄을 설 때 먼저 온 사람이 먼저 들어감)

- 나중에 온 사람일수록 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유됨

- 이러한 구조를 선입선출 (FIFO)라고 함

- 파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용

- deque는 스택과 큐의 장점을 모두 채택, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단

 

재귀 함수 (Recursive Function)

- 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미

- 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 함

- 자칫 종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있음

- 재귀 함수의 수행은 스택 자료구조를 이용 (함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문)

- 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있음