<PART2> 스택/큐/재귀함수

탐색: 많은양의 데이터 중에서 원하는 데이터를 찾는 과정
대표 탐색 알고리즘인 DFS/BFS를 이해하려면 기본 자료구조인 스택,큐,재귀 함수에 대한 이해가 전제되어야 합니다.

자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됩니다.
-삽입(push): 데이터를 삽입한다.
-삭제(pop): 데이터를 삭제한다.

push를 할 때는 오버플로우, pop을 할 때는 언더플로우를 조심해야합니다.

- 스택 (Stack)
선입후출 또는 후입선출의 구조이다. LIFO(Last in First Out)라고도 한다.

파이썬 코드로 표현하면 다음과 같다.

append와 pop자체가 서로 맨 뒤쪽 데이터를 push,pop하는 것이기 때문에 스택은 별도의 라이브러리가 필요하지 않습니다.

- 큐 (Queue)
큐는 대기 줄에 비유할 수 있다. 먼저 들어온 사람이 먼저 나가고 나중에 들어온 사람이 나중에 나가서 '공정한'자료구조라고 비유된다.(물론 새치기가 없다고 가정한다.) 그래서 선입선출 구조라고 한다. FIFO(First in First Out)라고도 한다.

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deaue 자료구조를 활용합니다. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러를 이용하는 것보다 더 간단합니다.
마지막에 deque객체를 list(queue)로 리스트 자료형으로 바꿔줄 수 있습니다.

- 재귀함수 (Recursive Function)
자기자신을 다시 호출하는 함수입니다. 함수를 계속 호출했을 때 가장 마지막에 호출된 함수가 먼저 수행을 끝내야  그 앞의 함수 호출이 종료되기 때문에 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조와 동일합니다. 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예입니다.

재귀적으로 구현하면 코드가 더욱 간결하게 표현할 수 있습니다.이는 점화식으로, 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하기 때문에 n이 1이하일 경우 1을 반환하도록 만들어야 합니다.