이숭간 공부기록

벨만포드 알고리즘 최단경로라는것은 같은정점을 두번 지날일이 없기때문에 최단 경로의 간선개수는 최대 V-1개이다. 따라서 루프를 V-1번 (V는 노드의수) 돌리는데(최악의 경우까지 모두 커버가 가능), k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어 ( 이렇기 때문에 음의순환을 찾을때 한번더 수행하는것 ) 음수간선이 포함된 상황에서 최단거리 찾기 모든간선이 양수일때는 다익스트라를 사용하면 된다. 음수 간선의 순환이 발생하는 경우, 최단거리가 음의 무한인 노드가 발생한다. (계속해서 줄일수있으니까 무한대로 순환) 간선에 관하여 최단 경로문제는 다음과 같이 분류된다. 모든 간선이 양수인 경우 ( 다익스트라, 플로이드 와샬) 음수 간..

한달동안 알고리즘문제에 손도 안댔더니.. 다 까먹어버린것같다.. 큰일났다.. DP (Dynamic Programming)이란? 큰 쿤제를 작은문제로 나누어 푸는것 동적 기억하기 프로그래밍 이라고 이해하는편이 좋겠다. DP와 분할정복의 차이 작은문제가 중복이 일어나는가 안일어나는가 분할정복 : 큰 문제를 작은문제로 나누어 푸는것은 맞지만, 작은문제들에서 반복이 없다!! DP : 작은문문제들이 반복되는것 (답이 바뀌지 않는) DP 적용방법 모든 작은문제는 한.번.만 푼다. -> 한번 구한 답을 어딘가 저장해놓는다. 이후에 다시 반복되는 작은문제가 나타나면 이미 구한답을 그대로 이용한다. DP의 조건 아래와 같은 조건을 만족하는 경우에 다이나믹 프로그래밍 풀이를 적용할수 있다. DP문제는 이 문제가 DP로 푸..

본 글은 동빈나 2021 이코테 _ 8. 기타그래프 이론을 정리한 글입니다! 서로소 집합 자료구조 _ Union-Find 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조(=합치기 찾기 자료구조)는 두종류의 연산을 지원한다. 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - Union의 인자값으로 각 노드가 들어감 - 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다. - 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다. 단, 여기서 부모..

출처 : gmlwjd9405.github.io/2018/05/10/data-structure-heap.html를 참고하여 작성하였습니다. " 우선순위 큐를 위해 만들어진 자료구조 " (우선순위 큐가 뭔데요? 우선순위의 개념을 큐에 도입한 자료구조로서, 우선순위가 높은 데이터가 큐에서 먼저 나가게 된다.) 1. 힙이란? 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조 여러개의 값중 최댓값이나 최솟값을 빠르게 찾아내도록 고안됨 부모노드의 키값이 자식노드의 키값보다 항상 크거나(혹은 작은) 이진트리이다. 힙 트리에서는 중복된 값을 허용한다. 2. 힙의 종류 최대힙 (Max Heap) key(부모) >= key(자식) 숫자로 생각하면 큐에서 나가는 순서가 내림차순이 되는것이다. 최소힙 (Min H..

모든노드에서 다른 모든노드까지의 최단경로를 계산한다. 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드중 최단거리를 갖는 노드를 찾는 과정이 필요없다. 2차원 테이블에 최단거리 정보를 저장한다. DP유형에 속한다. 플로이드 워셜 알고리즘 노드의 개수가 많은경우에는 플로이드워셜보다 다익스트라를 사용하는것이 좋다. 시간복잡도는 O(n^3)임 행은 출발노드, 열은 도착노드를 의미함. k값만 바꿔가면서 모든a,b를 반복하며 전부 확인해주면 된다. k = 1일때(1번노드를 거치는) 모든 a,b에 대해서 확인하고 갱신한다. 소스코드 import sys input = sys.stdin.readline INF = int(1e9) n = int(input..