파이썬2 [알고리즘 분석 #5] 1916 최소비용구하기 (파이썬) 알고리즘 다익스트라 알고리즘 BFS랑 구조가 비슷하다. 단, 해당 문제는 "비용" 이 들어가기 때문에 graph: 그래프의 간선을 저장하는 2차원 배열 costs: index 위치의 최소비용 저장 1차원 배열 2가지가 필요하다 BFS와 차이점은 방문여부를 따로 관리하지 않는다 이를 비용이 저장되있는것보다 더 크면, continue함으로써 비용 절약을 한다. 이를 통과하면 graph 배열을 통해 갈수있는 간선을 확인하고, 거쳐서 가는 비용이 더 적다면 갱신하고 q에 넣는다 기본 코드 import heapq # 우선순위 큐 구현을 위함 def dijkstra(graph, start): distances = {node: float('inf') for node in graph} # start로 부터의 거리 값을.. 2023. 2. 23. [알고리즘 분석 #4] 백준 1987 알파벳 ( 메모리 초과, 시간 초과, Python ) 미친것 같다. 문제 링크: https://www.acmicpc.net/problem/1987 시간초과 및 메모리 초과 해결법 1. 값을 빨리 찾는것은 List 의 In 은 O(n) SET은 O(1) 2. 재귀 횟수도 잘 고려해 보아야한다 만약 10**9로 하면 시간초과 난다 sys.setrecursionlimit(10000) 3. 처음에 visited 라는 방문 여부를 확인하는 배열을 넣어놨는데, 어차피 똑같은 알파벳이 있으면 돌아가지 못함으로 해당 배열을 빼도 된다. 코드 import sys import time sys.setrecursionlimit(10000) input = sys.stdin.readline n, m = map(int, input().split()) visit = set() grap.. 2023. 2. 22. 이전 1 다음
