본문 바로가기

⭐ Personal_Study/Algorithm4

Segment Tree Segment Tree Segment Tree란? ✔ 어떤 데이터가 존재할 때, 특정 구간의 결과값을 구하는데 사용하는 자료 구조! ✔ prefix sum? -> 유용하지만 값의 변경에 취약하다 ✔ 따라서 segment tree는 이진 트리 구조를 가진다! ✔ 목표로 하는 값을 최대로 커버하는 범위의 segment들을 더해서 합을 구한다 ✔ 값 변경 시에 자식 노드의 값만 바꾸면 되기 때문에 logN 시간 복잡도로 대응할 수 있다! 전체 코드 (재귀적으로 구현) from math import log2, ceil, gcd class SegmentTree: def __init__(self, input_list, calculation_method='sum'): self.level = 0 self.. 2022. 12. 3.

[알고리즘] 다익스트라 (Dijkstra) 다익스트라 (Dijkstra) 다익스트라 알고리즘이란 ✔ 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 다익스트라 알고리즘의 원리 * P[a][b]: a와 b 사이의 거리 출발점으로부터 최단거리를 저장할 배열 distance[v]을 만들고 출발 노드는 0, 나머지 노드들은 충분히 큰 값으로 초기화 한다. 현재 노드 Current를 출발 노드의 번호로 설정한다. Current로부터 갈 수 있는 임의의 노드 Next에 대해 distance[Current] + P[Current][Next](A를 거쳐서 B로 가는 최단거리)와 distance[Next](현재까지 알려진 B의 최단 거리)의 값을 비교해서 짧은 값(짧은 경로)로 갱신한다. Current의 모든 이웃노드 N.. 2022. 10. 1.

[알고리즘] 최소 신장 트리 (MST) 최소 신장 트리 (MST) 신장 트리 (Spanning Tree) ✔ 그래프 내의 모든 정점을 포함하는 트리 ✔ 그래프의 최소 연결 부분 그래프 (N - 1)개의 간선 -> 트리 형태 최소 신장 트리 (Minimum spanning Tree) ✔ Spanning Tree 중에서 간선의 가중치 합이 최소(Minimun)인 트리 ✔ 최소 신장 트리는 여러 개 일 수 있다. MST 구현 - 크루스칼 알고리즘 ✔ Greedy를 이용해 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 동작 순서 간선을 오름차순으로 정렬한다. (최소 비용) 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. (Union - Find 이용: Union-Find 알고리즘이란?!) 선택한 간선을 현재 .. 2022. 9. 29.

[알고리즘] Union-Find 유니온파인드 알고리즘이란 ✔ 서로소 집합(Disjoint Set) ✔ 여러 개의 노드가 존재할 때 , 임의의 두 노드가 같은 그래프에 속해있는지 판별 Union & Find Find 노드 x가 포함된 집합을 찾는 연산 def find_parent(parent, current): if parent[current] != current: return find_parent(parent, parent[current]) return current Union 노드 x가 포함된 집합과 노드 y가 포함된 두 집합을 통합하는 연산 def union_parent(parent, x, y): x = find_parent(parent, x) y = find_parent(parent, y) # 단순한 형태에서는 작은 쪽으로 합친다.. 2022. 9. 28.

이전 1 다음

티스토리툴바