알고리즘5 [알고리즘] 최소 공통 초상(LCA) Lowest Common Ancestor 한국말로 직역하면 최소 공통 조상이다. 자료구조 트리에 사용하며, 트리 내 두 노드 u, v의 공통 부모 중 가장 가까운 노드를 찾고자 할 때 사용할 수 있는 알고리즘의 한 유형이다. 간단한 그림으로 LCA의 한 예시를 보여주겠다. 1번 노드를 루트노드로 하는 위와 같은 트리가 있을 때, 6번 노드와 5번 노드의 최소 공통 조상인 LCA(5, 6)은 2번 노드이다. LCA의 정의에 대해서 간단히 살펴봤으므로 다음은 LCA가 어떻게 동작하는지 알아보겠다. 일반적으로 트리 관련 문제에서는 두 정점을 잇는 간선에 대한 정보가 주어진다. 그리고 간선에 대한 정보를 사용하여 이중 배열 또는 리스트 타입 배열 객체를 사용하여 전체 트리 구조를 저장할 수 있다. 만약 처음부터.. 2023. 6. 11. [알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 간단하게 DFS 혹은 BFS로 구현한 경우 출발 지점에서 도착 지점까지 하나의 경로에 대한 최단 경로를 확인할 수 있던 것에서 확장하여 출발 지점에서 이동할 수 있는 모든 지점에 대한 최단 경로를 알아낼 수 있다. 다익스트라 알고리즘을 적용할 수 있는 자료구조는 그래프이고 동작 단계는 다음과 같다. 1. 그래프 상의 모든 정점과 간선, 가중치에 대한 정보를 저장한다. 2. 최단 거리 테이블(dp)을 초기화 한다. 이때 dp에는 허용할 수 있는 가장 큰 수 + 1가 저장되어 있다. 3. 출발 노드에 대한 정보를 A에 저장한다(보통은 A = 우선순위 큐). 4. A에서 누적 가중치가 가장 작은 경로에서 (초기에는 출발노.. 2023. 6. 6. [알고리즘] 위상 정렬 순환 그래프와 비순환 그래프 정점 간의 연결관계를 표현하는 그래프가 내부에 순환 구간을 가지고 있으면 순환 그래프, 그렇지 않다면 비순환 그래프라고 한다. DAG(Directed Acyclic Graph) 비순환 방향 그래프라고 부른다. 명칭에서 유추해볼 수 있듯이 간선이 방향성을 가지는 비순환 그래프를 의미한다. 따라서 어느 한 정점으로부터 간선을 따라 출발하면 다시 해당 정점으로 돌아오는 경로는 존재하지 않는다. Topological Sort 위상 정렬이라고 부르며, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주고자 할 때 사용하는 알고리즘이다. 주변에서 볼 수 있는 예시로는 대학교에서 커리큘럼대로 강의를 수강하거나, RPG 게임 속의 스킬트리대로 스킬을 찍는 경우이다. 스킬 트.. 2023. 5. 24. [알고리즘] 유니온 파인드(Union Find) Union Find - 유니온 파인드 - 그래프 자료구조에서 주로 사용하는 알고리즘 - 두 노드가 같은 그래프에 속하는지 판별 - 서로소 집합(Disjoin-Set)으로도 불린다. - 노드를 합치는 Uion 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다. - 트리 구조로 이루어진 자료구조 중 한 가지로 생각되기도 한다. 그래프에서 임의의 두 정점이 연결 그래프인지 확인하고 싶다면 그래프를 순회하며 두 정점이 연결 되어 있는지 확인해 볼 수도 있지만 많은 정점에 대해서 동일한 작업을 반복하면 오랜 시간이 걸릴 것이다. 그러나 그래프의 일부분을 일종의 트리로 보고 공통의 루트 노드를 같는 노드끼리 하나의 집합으로 본다면, 두 노드에 대한 부모 노드의 동일 여부만 알아도 그래프의 모든 정점을 순.. 2023. 5. 24. [알고리즘]최소 신장 트리(Minimum Spanning Tree) 연결그래프 모든 정점이 연결되어 있는 그래프를 연결 그래프라고 부른다. 여기서 '연결되어 있다'라는 것의 의미는 인접한 정점만을 의미하는 것이 아니라 다른 정점을 거쳐서 도달 할 수 있음을 포함한다. 반대로 어느 두 정점을 골랐을 때 상호간에 도달할 수 없는 경우가 존재하는 그래프를 비연결 그래프라고 한다. Spanning Tree 무방향 연결 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프를 의미하며 신장 트리라고도 부른다. N개의 정점을 가지는 그래프의 최소 간선의 수는 N-1 개이고, 신장 트리의 간선 수는 언제나 N-1개가 된다. 신장 트리를 찾는 방법은 DFS, BFS 등이 있고 하나의 그래프에는 복수개의 신장 트리가 존재할 수 있다. 이런 신장 트리를 적용할 수 있는 분야는 사내 통신 .. 2023. 5. 22. 이전 1 다음
