알고리즘 | queue(FIFO) 속도이슈를 해결할 수 있는 deque
from collections import deque 디큐는 속도가 빠른 리스트로 생각해도 좋다. 코딩 테스트에서 파이썬으로 Queue, BFS, FIFO 방식의 알고리즘 접근이 필요할 때 리스트를 디큐로 바꾸어주면 속도 이슈 해결이 가능하다. a_list = [1, 2, 3, 4, 5] # [1, 2, 3, 4, 5] a_dq = deque(a_list) # deque([1, 2, 3, 4, 5]) 이렇게 간단하게 디큐 함수로 바꾸어주기만 하면 된다. a_dq.pop() a_dq.popright() # 5 a_dq.popleft() # 1 a_dq # deque([2, 3, 4]) a_dq.append(1004) # deque([2, 3, 4, 1004]) 디큐 맨 마지막 값을 뺄 때 : .pop() ..
2024. 4. 1.
알고리즘 | 탐색 기본, DFS / BFS
엣지를 따라 모든 노드를 방문하는 것을 그래프 탐색이라고 한다. 대표적으로 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있다. Depth First Search (깊이 우선 탐색) 깊이 우선 탐색은 기본적으로 Stack이다. (Last In First Out) 오른쪽 왼쪽 상관은 없음 예제 graph_list = [ [], # 0번 도시(없음) [2, 3, 8], # 1번 도시 [1, 7], # 2번 도시 [1, 4, 5], # 3번 도시 [3, 5], # 4번 도시 [3, 4], # 5번 도시 [7], # 6번 도시 [2, 6, 8], # 7번 도시 [1, 7] # 8번 도시 ] 1번 도시 방문 To do : [2, 3, 8] 2번 도시 방문 To do : [1, 7] -> 1번은 됐고 7번 ..
2024. 4. 1.
