자료구조와 알고리즘 - 최소 신장트리(MST, Minimum Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)

1. 신장 트리와 최소 신장트리 1.1 신장 트리 신장 트리는 위와 같은 무방향 그래프에서 모든 정점을 포함하면서, 사이클이 없는 연결된 부분 그래프를 말합니다.  즉, 신장 트리는 그래프의 모든 정점을 포함하며, 간선의 수는 정확히 V - 1개입니다(여기서 V는 정점의 수). 이는 트리가 가지는 기본적인 성질로, 사이클이 없으면서 모든 정점을 연결하는 구조를 의미합니다. 신장트리는 아래와 같이 여러개를 가질 수 있습니다.  1.2 최소 신장 트리 최소 신장 트리는 신장 트리 중에서 간선의 가중치 합이 최소인 트리입니다. 예를 들어, 위의 경우 가중치 합이 11인 신장 트리가 최소 신장 트리입니다 (2+2+3+1+3=11). 이때 최소 신장 트리를 구하는 알고리즘 중의 하나가 크루스칼 알고리즘입니다.  ..

• format_list_bulleted 컴퓨터/자료구조와 알고리즘
• · 2024. 9. 1.
• textsms

자료구조와 알고리즘 - 세그먼트 트리(Segment Tree)

1. 구간합과 누적합 문제1) 구간 합(Range Sum) 구간 합 문제는 주어진 배열에서 연속된 특정 구간의 합을 계산하는 문제입니다. 예를 들어, arr = [2, 4, 6, 8, 10]라고 할 때 - 인덱스 1~3까지의 합 = arr[1] + arr[2] + arr[3] = 4 + 6 + 8 = 18- 인덱스 0~3까지의 합 = arr[0] + arr[1] + arr[2] + arr[3] = 2 + 4 + 6 + 8 = 20  위와 같은 방식으로 구한 구간합 방식의 시간복잡도는 얼마나 될까요. 배열의 길이를 n이라고 하고, 구하고자 하는 구간합의 범위를 a에서 b까지(a, b ≤ n)라고 할 때, 구간합을 계산하기 위해서는 a, a+1, a+2, ..., b까지의 모든 원소를 더해야 합니다. 이러한..

• format_list_bulleted 컴퓨터/자료구조와 알고리즘
• · 2024. 7. 10.
• textsms