[플로이드 워셜 알고리즘] 모든 노드에서 다른 모든 노드 까지 최단 경로를 모두 계산한다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없게 됐다. 각 단계마다 \( O(N^2) \) 의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 시간 복잡도는 \( O(V^2) \) 다이나믹 프로그래밍 유형에 속합니다. K 번째 단계에 대한 점화식 : \( D_{ab} = min(D_{ab},D_{ak} + D_{kb} ) \) - A에서 B로가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신 INF = int(1e9) n, m = map(int,input().split()) # 노드의 갯수, 간선의 갯수 graph = [[INF]*(n+1) for _ ..
알고리즘
[간단한 다익스트라 최단 경로 알고리즘] 음의 간선이 없을 때 정상적으로 동작한다. 실제로 GPS 소프트웨어의 기본 알고리즘으로 많이 채택된다고 한다. 다익스트라는 최단 경로를 다루는 알고리즘이지만 코테에는 최단 거리가 주로 나오기 때문에 일단 최단 거리만을 책에서 다루겠다고 한다. 노드 1을 출발점으로 해서 최단 거리를 찾아나간다. 노드 1과 이어진 가장 짧은 간선을 찾는데, 다른 노드까지는 현재 무한으로 초기화 된 상태이다. 이미 탐색한 노드를 제외하고, 탐색하지 않은 노드 중 출발지로 부터 거리가 가장 가까운 노드부터 해서 탐색해나가며, 최단 거리를 갱신한다. 거리가 최솟값인 지점부터 탐색하기 때문에 이미 탐색한 노드와의 거리는 굳이 갱신할 필요가 없게 된다. ( 빨간색으로 표시 ) => 마지막 노..
[1로 만들기] 정수 X를 입력해, 5 로 나누거나, 3으로 나누거나, 2 로 나누거나, 1을 빼는 연산을 반복하여 1을 갖겠끔 하는 최단 연산의 갯수를 구하시오 도식화를 해보고 느낀 점은 1부터 해서 바텀 업 연산을 해야겠다. 1부터 X값 까지 최단 연산의 갯수를 다 구하면 되지 않을까? 근데 어떻게 연산 갯수 세는걸 어떻게 구현해야할지 모르겠어서 책을 봤다. ( 졸면서 5시간 고민 했는데 점화식이라는 개념이 미쳐 떠오르지 않았다. ) 점화식을 구해서 : \( a_i = min(a_{i-1},a_{i/2},a_{a/3},a_{a/5})+1 \) 점화식을 토대로 소스 코드를 작성한다. def sol(X): # df 테이블 초기화, d[1] = 0 d = [0]*(X+1) for i in range(1,X..
저희 스터디에서 학습 진도에 관해 제가 발표할 차례가 되어 발표 자료를 다음과 같이 만들었는데 그걸 가지고서 다이나믹 프로그래밍을 정리해보고자 합니다. [피보나치 수열을 통한 개념 설명] 효율적인 알고리즘! 이라고 간단히 표현할 수 있겠다. 예시) def fibo(x): if x=1 or x=2: return 1 return fibo(x-1) + fibo(x-2) fibo(6)을 호출해 봅시다. 중복되어 사용되는 코드가 보이시나요? 바로 이러한 중복된 코드 등을 줄임으로써 코드를 효율적으로 만드는걸 DP이라고 합니다. [다이나믹 프로그래밍] 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답이, 그것을 포함하는 큰 문제에서 구한 작은 문제에 대한 정답과 같다. 위 두 조건을 만족할..
