[dfs/bfs] 개념공부 with 파이썬

스택 구현 -> 파이썬의 list 적합.

.append() , .pop() 메서드의 시간 복잡도는 O(1) 이므로 스택 자료구조로 활용하기 적합하다.

 

큐 구현 ->  파이썬의 deque 적합. list보다 시간복잡도가 낮다.

list의 append와 동일하게 동작. 상수시간.

popleft는 가장 먼저 들어온 자료를 꺼내는 함수. 마찬가지로 상수시간.

 

재귀함수 ->  스택 대신 사용할 수 있음

-> 실제 코테중 콜백 수 제한이 있어서 당황해서 dfs 문제를 포기해 버렸다..!

이번 기회에 큐 및 스택으로 문제 푸는 법을 익히고 싶다.

--> 파이썬에서는 최대 재귀 깊이가 정해져 있기 때문에 초과 메시지가 출력된다고 한다..! -> c++만 쓰다가 파이썬이 처음이라 몰랐다..!

재귀 제한을 느슨하게 만들거나 스택 객체를 만들어서 사용할 수도 있다.

- 팩토리얼 구하기

- 최대공약수 계산(유클리드 호제법)