개발블로그by페페

if (depth[a] < depth[b]) { int temp = a; a = b; b = temp; } 왼쪽은 box이며, Label이고 오른쪽은 value 이다

기본 방법 - 루트 노드에서 BFS or DFS를 시작해, 각 노드의 부모 노드와 깊이를 저장 - 깊이가 다른 경우 더 깊은 노드의 부모 노드를 1개씩 올려주면서 같은 깊이로 맞춤 *PipeLine 만약 두 노드가 같게 나온다면, 해당 노드가 LCA이므로 탐색 종료 - 깊이가 맞춰진 상태에서 동시에 부모 노드로 올라가면서 누 노드가 같아질 때까지 반복 if (2 !== 3) > 시행 최소 공통 조상 빠르게 구하기 - 깊이를 맞춰 주거나, 부모 노드로 한 단계씩 올라갈때 한 단계 > 2^k 씩 올라가 비교하는 방법 - 기존 부모 노드만 저장해 두던 방식에서 2^k번째 위치의 부모 노드도 추가로 저장할 것 - P[K][N] N번 노드의 2^K번째 부모 노드 번호 - 점화식 P[K][N] = P[K-1][P[..

원리 방향 방법 N개의 배열값들 트리 최하부 리프단 오른쪽 절반에 몰아넣는다 A[2^k] ~ A[2^(k+1) -1] 0 ~ 2^(k-1) 구간인 위로 올라가면서 값을 저장, 요구하는 값을 편하게 load 가능 2N, 2N+1 > 부모인 N에 저장 자식 노드 2쌍이 부모 노드의 값에 영향을 미치는 구조 구간값 계산시 start가 왼쪽 리프쌍에 위치한다면, 부모 노드는 해당 자식 노드값을 포함되므로 선택하지 않는다 end index가 오른쪽 리프쌍에 위치한다면, 부모 노드는 자식 노드값을 포함하므로 선택하지 않는다 start / 2 == 1 > 선택 end / 2 == 0 > 선택 부모 노드로 이동하면서 선택한 것 누적 계산하기 start는 오른쪽 위 부모노드로 end는 왼쪽 위 부모노드로 start = ..

모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 > 가중치가 작은 에지부터 에지가 N-1개가 될 때까지 연결하되(정렬 > union) > find로 대표 노드가 같으면(왼쪽 방향 회전(find로 찾아진 대표 노드)이 오른쪽 새 연결과 만날 때) 사이클이 생기므로 건너뛴다 - 사이클이 포함되지 않는다 - N개의 노드가 있을 때, 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개이다 - 에지 중심의 시행 ------------------------------------ 1 재료 edge list 형태로 저장 edge class에는 Node-start, Node-end, weight로 구성 union find 배열도 초기화 2 가중치 기준으로 오름차순 정렬 comparable()..

모든 노드 간 최단 경로 탐색 - 음수 w 있어도 수행가능 - Dynamic programming 이용 단 하나의 맥락 - A~B 사이의 최단 경로 위에 K노드가 존재한다면, K로 들어가고 나오는 경로 역시 최단 경로 - D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1 D[S][E](Adjacency matrix) 선언 후 > S == E일 때 0 > 나머지 = INF 2 D[S][E] = W 저장 3 3중 for문의 형태로 반복 > 업데이트 for (k : 1~N) { for (S : 1~N) { for (E : 1~N) { D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]); } } }

2022.08.08 - [Track Phase-Turnovering/algorithm 100] - 059 : 타임머신으로 빨리 가기 출발 노드에서 다른 모드 노드까지 최단 경로 탐색 - 음수 w가 있어도 수행 가능 - 에지 중심 시행 - 전체 그래프에서 음수 사이클의 존재 여부 판단 가능 1 edge list graph and D[index] - ArrayList edges > s, e, w - D[1] = 0, D[2~N] = ∞ 2 모든 에지를 확인, 정답 배열 업데이트 - if (D[s] != ∞ && D[s] + w D[e] = D[s] + w - 음수 사이클이 없을 때, 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 수는 N-1 3 음수 사이클이 존재하는 지 확인 - 모든..

출발 노드와 모든 노드 간의 "최단 거리" 탐색 - weight가 있을 때 - 에지는 모두 양수일 때 0 Adjacency matrix로 구현해도 좋지만, 시간 복잡도 및 N의 크기에 대비해 Adjacency graph로 구현한다 1 최단 거리 배열 D[N]을 만들고 - 출발 노드 0 - 나머지 노드는 Integer.MAX_VALUE로 할당 2 cycle unit - D[N]에서 가장 값이 작은 노드를 고른다(출발 노드에서 시작) - 해당 노드와 연결된 노드에 에지의 가중치를 업데이트 - Min(D[selected] + edge weight, D[connected]) 3 kaiten space - 모든 노드가 선택될 때까지 반복 - boolean[] visited를 만들어 중복 처리 - 출력

- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 - 우선 순위와 관련 - ArrayList[N]을 사용 1 : 진입 차수(in-degree) - indegree D[N]을 만든다 - 인접 리스트에서 노드와 edge 값이 할당되면, 에지인 D[i] 값을 올려준다(D[i]++;) 2 : cycle unit 진입 차수가 0인 노드를 Queue에 저장한다 해당 노드와 연결된 edge의 D[i]를 1씩 감소시킨다(D[i]--;) 3 : 다음 노드인 2를 선택 모든 노드가 정렬될 때까지 반복 4 : 정렬 결과를 출력

union : 특정한 2개의 노드를 연결해 1개의 집합으로 묶음 find : 두 노드가 같은 집합에 속해 있는지 체크 1차원 배열을 이용 index = 값 value = 대표 노드(집합) find :4 index와 value 가 동일한지 확인한다 // union public static void union(int a, int b) { a = find(a); b = find(b); if (a != b) { label[b] = a; } } // find public static void find(int a) { if (a = label[a]) return a; else return label[a] = find(label[a]); } // checkSame public static boolean checkSa..

Edge list A[2][N] 노드를 배열에 저장하여 에지를 표현 배열에 출발 노드, 도착 노드, (가중치) 를 저장 > - 특정 노드와 관련 있는 에지를 탐색하기는 쉽지 않음 - 노드 중심 알고리즘 x - 벨만 포드 / 크루스칼 사용 Adjacency matrix A[N][N] 노드 중심의 그래프 표현 - 노드와 관련된 에지 탐색시 N번 접근해야 하므로, 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 - 노드 갯수가 많은 경우 2차원 배열 선언이 불가한 결함(노드가 3만개가 넘으면 heap space 에러 발생) Adjacency List ArrayList[N] - 노드 개수만큼 ArrayList를 선언 - 에지 탐색 시간은 빠름 - 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 ..