Leta Learns

오일러 경로 (Eulerian Trail) : 그래프에 존재하는 모든 엣지를 1번씩만 방문하는 연속된 경로 if 시작점 == 도착점 : 오일러 회로 (Circuit) 별 모양 그래프 : 대표적인 오일러 회로 시작점이 어디든 모두 출발점으로 되돌아 온다. 모든 정점의 차수 : 2 (짝수) => 들어오는 간선이 있으면, 나가는 간선도 있어야 하므로 (시작점, 끝점 제외) => 항상 차수가 2의 배수 꼴로 붙는다. 무향그래프인 경우 차수(Degree)가 홀수인 정점이 2개 -> 오일러 경로 0개 -> 오일러 회로 오일러 회로가 존재한다면, 어떤 정점을 시작점으로 선택하든 오일러 경로를 만들 수 있다. 오일러 회로 구하기 현재 가장 널리 알려져있고, 가장 효율적인 알고리즘 : Hierholzer’s Algori..

Segment Tree : 사용자가 요청한 쿼리에 대해서 더 빠르게 응답하기 위해 만들어진 자료구조. 특정 기준으로 트리를 전처리하여 연산 속도를 높이게 된다. 이진 트리 구조. 구간 트리라고도 불림. 배열로 구현 가능. 세그먼트 트리를 이루는 각 노드의 왼쪽 자식과 오른쪽 자식이 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현. => 이진 트리 구조 Segment Tree를 사용하는 이유 배열 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 있는 경우. arr[4] + arr[5] + arr[6] 의 부분합을 구하는 쿼리와 arr[4]의 값을 바꾸는 쿼리가 있다고 하면 보통의 방식에서 부분합을 구하는 쿼리는 O(N), 값을 바꾸는 쿼리는 O(1)의 시간복잡도를 요구한다. 이처럼 수..

LCA (Lowest Common Ancestor) 알고리즘 : 최소 공통 조상을 찾는 알고리즘 즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘 Segment Tree를 사용한 방법, DP를 사용한 방법이 존재하는데 DP 사용법에 대해서 공부하였다. 9와 6의 최소 공통 조상 : 2 4와 10의 최소 공통 조상 : 8 2와 15의 최소 공통 조상 : 1 LCA 접근법 최소 공통 조상 찾는 방법 : 각 노드에서 부모를 타고 올라가서 같은 부모를 찾는다. 이때, 양 노드의 레벨이 같아야 함. => 각 노드의 부모와 레벨을 알아야 하고, 트리가 있어야 함 각 노드의 부모 노드, 레벨 저장하는 법 => DFS 사용 재귀를 한 번씩 돌 때 마다 레벨 += 1, 부모 노드 또한 저장 가능. ex) 6과 1..

최단 경로 알고리즘 (Shortest Path) 그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다. ( != MST ) MST : N-1개의 간선으로 최소 가중치 트리 만듦 그래프 내의 모든 간선의 가중치가 0 이상인 경우 => Dijkstra 알고리즘을 이용한다. 그래프가 음수 가중치 간선을 포함하는 경우 => Bellman-Ford 알고리즘을 이용한다. Dijkstra 알고리즘 출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고, 다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서 가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신. (음의 간..

Bellman-Ford Algorithm : 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 가중치가 음수일 때도 사용 가능 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수인 경우 굳이 벨만포드 사용할 필요 x. 다익스트라 쓰면 됨. Bellman-Ford 알고리즘의 특징 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 음수 사이클 존재 여부를 알 수 있다. => 그래프 정점 개수를 v라고 할 때 인접 간선을 검사하고 거리 값을 갱신 (갱신 과정은 v-1번으로 제한) => 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거치는 최대 간선 수: v-1개 => v번째 간선이 추가되면 사이클이라고 판단 Bellman-Ford 과정 1. 시작 정점 결정..

1. Tree DP Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나) => 그래프처럼 DP 기법 적용 가능 트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다. 트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적. => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함. 기본적으로 Top-down 방식으로 코드 작성. => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식. Tree DP 예제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 ..

Union - Find (합집합 찾기) 대표적인 그래프 알고리즘 상호 배타적 집합 (Disjoint-Set) 알고리즘 (서로소 집합) 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 이 두 노드가 서로 같은 그래프에 속하는지 판별 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 그림으로 이해하기 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다. i : 노드번호 P[i] : 부모 노드 번호 ( => 자기 자신이 어떤 부모에 포함되어 있는지를 의미, parent) 지금 현재는 모든 값이 자기 자신을 가리키므로 P[i] = i 이다. Uni..

Kruskal Algorithm : 그리디 방법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 간선 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리와 무관하게 무조건 최소 비용 간선 선택 Kruskal 알고리즘 과정 그래프의 간선들을 가중치를 기준으로 오름차순 정렬 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택 -> 최소 가중치 먼저 선택, 사이클 형성하는 간선은 제외 해당 간선을 현재의 MST 집합에 추가 Kruskal 알고리즘 예 주의할 점 ! 간선을 선택할 때 사이클을 생성하는지 확인 => 추가할 간선의 양 정점이 같은 집합에 속하면 안 된다. 사이클 생성 여부 확인 방법 :..

Prim 알고리즘 대표적인 최소신장트리 알고리즘 ex) Prim, Kruskal 알고리즘 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치로 연결된 정점을 선택. 해당 정점에서 다시 최소 가중치로 연결된 정점을 선택. => 그리디 알고리즘 Prim 알고리즘 예 임의의 정점을 선택. 연결된 노드 집합에 삽입. 현재 정점에 연결된 간선들을 간선 리스트에 삽입 간선 리스트에서 최소가중치를 가지는 간선 추출 추출한 간선은 간선 리스트에서 삭제 간선 리스트에 더 이상 간선이 없을 때 까지 3,4번 반복 3번 과정에서, if 해당 간선에 연결된 정점이..

Spanning Tree (신장 트리) : 그래프의 최소 연결 부분 그래프. 최소 연결 -> 간선의 수가 최소 n개의 정점을 가지는 그래프의 최소 간선의 수: n-1 n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. => ST 즉, 그래프에서 일부 간선을 선택해서 만든 트리. Spanning Tree의 특징 하나의 그래프에는 여러 개의 신장 트리가 존재 가능. ST는 트리의 특수 형태 => 모든 정점들 연결 => 사이클 포함 x => N개의 정점을 정확히 n-1개의 간선으로 연결 Minimum Spanning Tree (최소 신장 트리) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 ..