내 잡다한 노트

하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이때 음의 간선을 포함할 수 없다. 그래서 모든 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾을 수 있다. 구현할 때 dp를 활용할 수 있다. dijkstra가 dp문제인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.' 기본적으로 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다. # 구체적인 작동 과정)) 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신 5. 3번~4번을 반복한다. ..

* 그래프에서 정점끼리의 최단 경로를 구하는 방법 1. 하나의 정점에서 다른 하나의 정점까지의 최단경로를 구하는 문제 start가 하나, arrival point가 하나 2. 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 start가 하나, arrival point가 여러개 3. 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 start가 여러개, arrival point가 하나 4. 모든 최단 경로를 구하는 문제 start가 여러개, arrival point가 여러개 플로이드 와샬은 마지막에 해당하는 모든 최단 경로를 구하는 방법이다. 다익스트라와 벨만포드는 두 번째에 해당.

트리가 존재할 때, 해당 노드의 N번째 앞에 있는 조상노드를 빠르게 찾기 위해 사용하는 알고리즘이다. (그래프에서도 사용할 수 있기는 하는 것 같다.) 기본 아이디어는 2의 N제곱으로 조상 노드를 log만큼 이동하는 것이다. 그래서 O(logN) 만에 N번째 조상 노드를 찾아갈 수 있다. 여기서 N이 0일때는 부모 노드를 가리킨다. 보통 2차원 배열로 표현을 한다. parent [logn+1][n+1] 크기로 만든다. 각 노드들의 부모 노드들은 0번 이동한 것이니 parent[0][i] 노드에 부모 노드들을 넣어준다. i번 노드의 2^0번째 부모노드니 바로 위의 부모 노드가 될 것이다. for i in range(1, logn+1): # 2^i번 부모 노드 for j in range(1, n+1): # ..

최소 공통 조상 # 정의 : 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 이 알고리즘을 만드는 방법은 2가지가 있다. 1. LCA를 선형 탐색으로 구하기 -> O(Depth) 2. LCA를 이분 탐색으로 구하기 -> O(log(Depth)) # LCA를 선형 탐색으로 구하기 공통 조상을 찾기위한 가장 단순한 방법으로는, 두 정점에 포인터를 두고 가리키는 정점이 같아질때까지 부모 노드로 거슬러 올라가면 된다. parent[x]를 정점 x의 부모 노드라 할 때, x = parent[x] 연산을 반복하다보면 두 개의 포인터가 같은 정점을 가리키게 됐을 때 공통 조상을 찾은 것이다. 주의할 점은 두 정점의 LEVEL이 다르다면 문제가 발생한다. 하나는 LEVEL이 3인데 다른 것은 ..

트라이(Trie) 알고리즘 # 개념 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 한다. retrival(탐색)에서 trie를 따왔다고도 한다. 이 자료구조를 활용해 검색어 자동완성, 사전에서 찾기, 문자열 검사 등을 한다고 한다. # 사용 목적 문자열의 탐색을 할 때, 단순하게 하나씩 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 훨씬 효율적이다. 단 빠르게 탐색이 가능하다는 장점이 있지만, 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다. 문자열을 검색하는 문제에서 입력되는 문자열이 많은 경우 자주 사용됨. # 시간 복잡도 제..

동적 프로그래밍 (브루트포스 + 이전 값 재활용) 분할정복 기법을 사용하는 경우가 많다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법이다. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생기는데 그 문제들을 매번 재계산하지 않고 값을 저장 해두었다가 재사용하는 기법이 동적 프로그래밍이다. 즉, 이미 했던 연산이 반복되는 결점을 보완하기 위해 쓰여지기 시작함 메모이제이션이 동적 프로그래밍 중 하나이다. 메모이제이션이란 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법이다. # 문제풀이 방식 문제풀이 방식으로는 TOP-DOWN, BOTTOM-UP 이 존재한다. top-down은 대부분..

'호'는 한자로 서로 호, '제'는 덜 제 라고 한다. 서로 두 수를 나눈다라는 뜻이라고 한다. - 최대공약수 - 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질을 이용해 반복해서 나머지가 0이 나올 때까지 나누면 그 수가 최대공약수라고 한다. function gcd(a, b) { let r while (b != 0) { r = a % b a = b b = r } return a } - 최소공배수 - a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다. function lcm(a, b) { return (a * b) / gcd(a, b) } 위에서 구한 최대공약수로 최소공배수는 쉽게 구할 수 있다..

언제 써야 하는가? ) '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다 핵심 아이디어 ) '거쳐가는 정점'을 기준으로 최단거리를 구하는 것. 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 저장한다. 저울 소스코드중... graph = [[INF] * (n + 1) for _ in range(n + 1)] for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 for _ in range(m): a, b = map(int, input().split()) graph[a][b] = 1 a -> b로 갈 수 있으면 1로 해주고 가지 못하는 방향이라면 INF로..