728x90 반응형 DFS2 최소 공통 조상 (Lowest Common Ancestor, LCA) 최소 공통 조상 (LCA) 알고리즘Problem Setup$N$개의 node로 이루어진 트리가 주어진다. (트리이므로 간선의 개수는 $N-1$개이다)$q$개의 query에 대하여 두 node사이의 거리를 계산한다. 위 그림은 백준 11437 LCA 문제이다. 1번 노드가 루트이다.6번과 11번 노드의 최소 공통 조상은 2번 노드이다. (1번 노드 역시 공통 조상이지만, 최소가 아니다.)10번과 9번 노드의 최소 공통 조상은 4번이다. 즉, LCA(10, 9) = 48번과 15번 노드의 최소 공통 조상은 1번이다. 즉, LCA(8, 15) - 1 루트노드에서 DFS/BFS 알고리즘을 통해 각 노드의 깊이를 계산하여 depth 배열에 저장한다.1의 depth는 0, 2와 3의 depth는 1, 4번~8번 노.. 2024. 7. 11. [CS246] MapReduce Large-scale Computingsupercomputer를 운용하는것은 너무 비용이 크고, 심지어 데이터 크기(scaling)를 크게 할 수 없다.대신, 하드웨어를 연결하여 분산처리를 구현한다. (collection of commodity hardware)Challengesdistribute computation?distributed programs?machines fail네트워크간 데이터 복사(copy)는 시간이 걸린다. local에 연산 결과를 저장하고, failure에 대비하여 여러번 저장한다.Spark/Hadoop은 이런 문제를 해결할 수 있다.Storage Infrastructure: Google File System (GFS), Hadoop Distributed File System (H.. 2023. 9. 8. 이전 1 다음 728x90 반응형
