Eunbi

최단경로 문제 가중치가 있는 그래프에서, 가중치의 합이 최소가 되는 경로를 찾는 것. 종류 단일 출발 / 출발지1, 도착지n : 하나의 노드에서 출발해, 여러 도착지를 방문할 때 어느 노드까지 가는 경로가 최단인지 찾는 문제 단일 도착 / 출발지n, 도착지1 : 여러개의 노드에서 출발해, 하나의 도착지를 방문할 때 어느 노드부터 출발해야 경로가 최단인지 찾는 문제. 출발지1, 도착지n의 위 경우의 간선 방향을 뒤집어서 똑같이 해결한다. 출발지n, 도착지n' : 여러개의 노드에서 출발해, 여러 도착지를 방문할 때 최단 경로를 찾는 문제. 가상의 출발 노드 하나를 만들어 (진짜 출발노드와 가상 출발노드를 잇는 간선이 필요한데 이때 간선의 가중치는 0임) 해결한다. 전체 쌍 / 출발지n, 도착지n : 모든 노..

LCA (Lowest Common Ancestor) 노드 A, B의 최소 공통 조상을 찾는 것. DFS/BFS를 수행해 트리의 각 노드 깊이와 부모 노드에 대해 저장한다. 노드 A, B의 부모를 따라 하나씩 올라가 (depth를 맞춘 상태로 시작) 최소 공통 조상을 찾는다. ===> 이는 $O(N)$만큼 걸림. 보다 빠르게 LCA를 수행하는 방법. parent[K][V]=parent[k-1][parent[k-1][V]] : V 노드의 $2^K$번째 조상 노드 (K, V의 순서에 따라 속도가 매우 달라짐. (2차원 배열의 구현특성 때문에)) 가로로 -> 이 방향으로 순회하는 것이 더 빠름. 우리가 갖고있는 정보. 한 노드의 바로 위의 부모 노드는 무엇인지 알고 있음. (parent[0][x]) 이때 par..

그래프 무향 간선 : 방향이 존재하지 않는 간선 유향 간선 : 방향이 존재하는 간선 인접 Adjacent : 정점A, B를 바로 잇는 간선이 존재한다면 A, B는 인접하다. 차수 Degree : 정점에 존재하는 간선의 수 in-degree : 정점에 들어오는 간선의 수 out-degree : 정점에서 나가는 간선의 수 그래프의 종류 무향 그래프 : 무항 간선으로 이루어진 그래프 유향 그래프 : 유향 간선으로 이루어진 그래프 가중치 그래프 : 가중치를 갖는 간선으로 이루어진 그래프 완전 그래프 : 임의의 두 정점에 대해 이를 잇는 간선이 존재하는 그래프 (모든 노드가 연결되어있고, 인접해있음) 연결 그래프 : 임의의 두 정점에 대해 이를 잇는 경로path가 존재하는 그래프 트리 그래프 : 순환(사이클)을 ..

펜윅 트리 누적합을 구한다. → 누적합을 이용하면 구간합도 구할 수 있음. 세그먼트 트리와 다르게 추가적인 공간(tree)이 필요없다. 만약 1~13번째 데이터의 구간합을 구하고 싶다면... 8, 12, 13번 값을 알면됨. 8 : 1~8까지의 값 12 : 9~12까지의 값 13 : 13의 값 LSB(Least Significant Bit) Index 정의하기 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 binary 0001 0010 0011 0100 - - - - - - - - - - - - LSB index 1 2 1 4 - - - - - - - - - - - - 저 칸수만큼 나를 기준으로 왼쪽을 커버. LSB 구하기 : v&-v 기존 이진수와 2의 보수를 and 연산하면..