Algorithm37 느리게 갱신되는 세그먼트 트리(Lazy Segment Tree) 목차 느리게 갱신되는 구간 트리(Lazy Segment Tree) 세그먼트 트리랑 개념은 동일하지만, Lazy 세그먼트 트리는 특장 인덱스 값 하나만 update하는 것이 아닌, 구간의 값을 한 번에 update 해주는 경우에 사용합니다. 해당 구간을 업데이트할때 바로 업데이트를 진행하는 것이 아닌, lazy에 값을 저장해두었다가, 나중에 해당 노드로 들어가게 된다면, 거기에서 그 노드를 업데이트를 진행시켜줍니다. 세그먼트 트리의 경우 update 할때마다 해당구간에 대해서 업데이트를 진행해주게 되면, 그 구간에 대한 인덱스들을 모두 업데이트를 진행해야하기때문에 시간이 오래 걸리게 됩니다. 리스트 길이가 N개고 쿼리가 Q개라고 한다면 결국 쿼리 한개당 구간에 대한 인덱스를 모두 업데이트를 진행해야하기때문.. 2024. 3. 20. 구간 트리(Segment Tree) 목차 구간 트리(Segment Tree) 세그먼트 트리는 구간 쿼리와 갱신(Update) 작업을 효율적으로 처리할 수 있는 자료 구조입니다. 배열의 특정 구간에 대한 정보(예를 들면 합, 최댓값, 최솟값)를 빠르게 계산하고, 배열의 원소가 변경될 때 이 정보를 쉽게 업데이트할 수 있도록 설계되었습니다. 리스트를 슬라이싱 해서 해당 구간의 연산을 자주 하는 문제가 있을 경우 세그먼트 트리를 이용하여 시간 단축이 가능합니다. 전체 배열의 개수가 N이고 (특정 리스트 슬라이싱 구간 연산) 쿼리의 개수가 Q라고 할 경우, 시간복잡도는 리스트 슬라이싱으로 O(N), 쿼리연산으로 O(Q)이므로 결국 O(QN)의 시간복잡도가 걸릴 것입니다. 반면, 세그먼트 트리를 사용하면, 초기 배열에 대한 트리를 구성하는 데 O(.. 2024. 3. 20. 최소 스패닝 트리(Minimum Spanning Tree, MST) 목차 최소 스패닝 트리(Minimum Spanning Tree, MST) / Union-Find 신장 트리(Spanning Tree)는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프를 의미함.(루트 노드가 없는 트리라고 생각) 트리 : n개의 노드, n-1개의 간선 (모든 노드가 연결, 순환이 없는 그래프) 신장 트리 : 루트노드가 없는 트리 최소 스패닝 트리(MST,minimum spanning tree) 그래프에 간선이 여러개 존재할텐데, 그중에서 스패닝 트리로 만들수 있는 모양중 가중치의 합이 최소가 되는 것 최소 스패닝 트리를 만드는 방법 (크루스칼 알고리즘, MST 알고리즘중 가장 많이쓰이고 빠른편) 먼저 간선을 가중치값을 오름차순으로 정렬 그후에 하나씩 연결을 진행하는데, 연결을 하는.. 2024. 3. 20. Union-Find 목차 Union-Find Union-Find 알고리즘은 두 요소가 같은 그룹에 속하는지를 판단하거나, 두 요소를 같은 그룹으로 합치는 연산을 효율적으로 수행하는 데 사용됩니다. 이 알고리즘은 그래프의 연결성을 확인하거나, 최소 스패닝 트리를 찾는 크루스칼 알고리즘과 같은 다양한 알고리즘에서 중요한 역할을 합니다. Union-Find 알고리즘은 다음 두 가지 주요 연산으로 구성됩니다. Find 어떤 요소가 속한 그룹(또는 집합)의 대표를 찾는 연산. 이 연산을 통해 두 요소가 같은 그룹에 속하는지 확인 가능 두 요소의 Find 연산 결과가 같다면, 두 요소는 같은 그룹에 속한다고 판단 가능 parent[x]를 찾는 과정 Union 두 그룹을 하나의 그룹으로 합치는 연산. 두 요소가 속한 그룹을 Union .. 2024. 3. 20. 이전 1 ··· 3 4 5 6 7 8 9 10 다음
