알고리즘2 [알고리즘] 최소 공통 조상(LCA) 알고리즘 🧩 최소 공통 조상(LCA) 알고리즘 최소 공통 조상(LCA): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 여기서 3번 노드와 11번 노드의 공통 조상 노드는 1번이다. ✔️ 동작 과정 모든 노드에 대한 깊이(depth)를 계산 최소 공통 조상을 찾을 두 노드를 확인 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다. 모든 LCA(a, b) 연산에 대하여 2번의 과정을 반복한다. 1) 모든 노드 깊이 계산 우선 DFS를 이용해서 루트 노드에서부터의 깊이를 구한다. 2) 공통 조상을 구할 노드 선택 두 노드의 깊이를 맞춰주고, 거슬러 올라간다. 그렇게 2번 노드가 공통 조상임을 찾을 수 있다! .. 2023. 12. 10. [알고리즘] 최단 경로 알고리즘 (다익스트라, 플로이드 워셜) 🧩 최단 경로 알고리즘 최단 경로 알고리즘: 가장 짧은 경로를 찾는 알고리즘 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 [그래프] 노드(각 지점) / 간선(지점 간 연결된 도로) 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작 그리디 알고리즘 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 ✔️ 동작 과정 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 위 과정에서 3번, 4번 .. 2022. 10. 25. 이전 1 다음 반응형
