python/알고리즘2 [알고리즘] 최단거리 구하기, 다익스트라 알고리즘 ● 자료구조 우선순위 큐 - 자료 중 최소 or 최대 값을 먼저 출력한다. (기본적으로 최소) - 라이브러리 heapq를 사용한다. - 입력(heapq.heappush(list, value), 출력(heapq.heappop(list)) ● 다익스트라 알고리즘 (시작 지점부터 최단거리를 구하는 알고리즘) 1. 경로가 가장 짧은 노드 부터 탐색 2. 최단 거리 list를 무한으로 설정한다. 3. 노드 중에서 가장 짧은 거리를 갖고 있는 노드를 방문한다. 4. 현재 노드와 연결된 노드들의 거리를 계산하고 최단거리 list를 갱신한다. 5. 3,4를 반복한다. 모든 노드를 방문할 때까지 ● 코드로 구현 import heapq graph = [[] for _ in range(n+1)] # 각 노드가 연결된 정보(.. 2021. 2. 20. [알고리즘] DFS/ BFS ● 자료구조 스택 & 큐 1. 스택 : 선입 수출의 구조를 갖는 자료구조 - 박스 쌓기에 비유할 수 있다. 마지막에 쌓은 박스를 먼저 꺼내야 아래 박스를 꺼낼 수 있다. - 일반적인 리스트 구조가 스택에 해당된다. (스택을 이용한 알고리즘을 사용할 때 일반 리스트 사용) - 입력(append), 출력(pop) 사용. 2. 큐 : 선입선출의 구조를 갖는 자료구조 - 대기줄처럼 먼저 들어온 데이터를 먼저 출력한다. - 라이브러리 collections에서 deque로 사용 가능하다. - 입력(append), 출력(popleft) 사용. ● DFS / BFS 1. DFS 깊이 우선 탐색 : 그래프에서 가장 깊은 곳을 먼저 탐색하는 방법 - 1번부터 인접한 노드를 DFS로 탐색하는 과정 - 위 과정을 반복하여 전.. 2021. 2. 13. 이전 1 다음
