전보
유형 파악 이 문제는 특정 노드에서 다른 모든 노드로 갈 때 최단 경로를 구하는 문제이다. 다익스트라 알고리즘이 적합하다. 내 개인적인 생각으로는 최단 경로 알고리즘들은 그냥 적용하면 된다. 코드 import heapq n, m, c = 3, 2, 1 graph = [ [], [[2, 4], [3, 2]], [], [] ] INF = int(1e9) distance = [INF]*(n+1) distance[1] = 0 q = [] heapq.heappush(q, [0, 1]) while q: dist, now = heapq.heappop(q) if dist > distance[now]: continue for i in graph[now]: next_node = i[0] next_dist = i[1] di..
Shortest Way - Concept
해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다. - 한 지점에서 다른 특정 지점까지의 최단경로를 구해야 하는 경우 - 모든 지점에서 다른 모든 지점까지의 최단경로를 구해야하는 경우 종류 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - ex) 노드1 to 노드 2, 3, 4, 5 - 시간복잡도 : O(ElogV) - 우선순위 큐 (heapq), distance 테이블 활용 플로이드 워셜 알고리즘 - 모든 노드에서 출발하여 모든 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘 - ex) 노드1, 2, 3, 4, 5 to 노드 1, 2, 3, 4, 5 - 시간 복잡도 : O(N**3) - 3중 for문 사용 - 비교..
정렬된 배열에서 특정 수의 개수 구하기
유형 분석 및 구현 이 문제는 직접 이진탐색을 구현한다기 보단, 파이썬에서 제공하는 이진탐색을 활용한 탐색 방법을 사용한다. 순차적 탐색과 비교해보면 최대 100만개에 데이터 중에서 최대 100만개의 데이터를 찾아야한다. 하지만 이진 탐색을 활용하면 확 줄어든다. 코드 from bisect import bisect_left, bisect_right n = 7 x = 2 array = [1, 1, 2, 2, 2, 2, 3] left_index = bisect_left(array, x) right_index = bisect_right(array, x) print(left_index, right_index) result = right_index-left_index if result == 0: print("-1..
