전체 글 (171) 썸네일형 리스트형 [최단 경로 트리] 다익스트라 알고리즘[Dijkstra] 다익스트라 알고리즘을 설명하기 전에, 최단 신장 트리에 대해 설명해보자. 신장 트리란 그래프 내의 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 트리이다. 따라서 신장 트리는 N개의 정점을 정확히 N-1개의 간선으로 연결하게 된다. 다익스트라 알고리즘은 출발 지점을 정하여, 다른 모든 지점까지의 최단 경로를 찾는 것이다. 예를 들어보면, A를 출발 지점으로 두고 시작해보자. A의 최단 거리값은 0으로, 나머지 최단 거리값은 무한으로 설정한다. 이제 A와 연결된 B, C의 거리 값을 조정하자. 여기서, 시작점 거리값 + 아크 값 < 도착점 거리값이라면, 도착점 거리값을 더한 값으로 낮춘다. 방금 했던 것을 무한 반복할껀데, 이번에는 B를 기준으로 한다. 최종적으로, 이런 결과가 나오게 된다. 거리가.. [BOJ] [Python] 18352번 : 특정 거리의 도시 찾기 다익스트라 알고리즘을 이용하여 풀었다. 처음에는 시간 초과가 났다. 통과하기 위한 과정을 아래에 적어놓았다. 아래는 통과한 코드이다. import sys import heapq input = sys.stdin.readline n, m, k, x = map(int, input().split()) route = [] val = [10000000] * (n+1) val[x] = 0 for n_c in range(n+1): route.append([]) for m_c in range(m): num = list(map(int, input().split())) route[num[0]].append(num[1]) order = [] # 순서 리스트 heapq.heappush(order, (0, x)) # (거리, 위.. [BOJ] [Python] 11053번 : 가장 긴 증가하는 부분 수열 앞에서부터, 각 값에 해당하는 최대 수열 위치를 저장하면 된다. 예를 들어, 50의 위치 최댓값을 고려할 때 1. 30의 3번 뒤 2. 25의 6번 뒤 당연히 2번을 선택해야 한다. 둘 다 값이 50보다 작기 때문에, 더 큰 수열 위치를 선택한 것이다. num = int(input()) li = list(map(int, input().split())) dp = [0] * len(li) for i in range(num): tmp = 0 for j in range(i): if li[j] < li[i] and tmp < dp[j]: tmp = dp[j] dp[i] = tmp dp[i] += 1 # self print(max(dp)) 이전 1 ··· 46 47 48 49 50 51 52 ··· 57 다음
