MST(최소 신장 트리, Minimum Spanning Tree)란?MST(최소 신장 트리, Minimum Spanning Tree)는 가중치 그래프에서 모든 정점을 연결하는 간선들의 부분 집합 중에서 최소 비용을 가지는 트리이다.즉, 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 부분 그래프를 의미한다.MST의 특징모든 정점이 연결되어 있어야 함 (Connected Graph)사이클(Cycle)이 포함되지 않음 (Tree)(N-1)개의 간선으로 구성됨 (N개의 정점을 가지는 그래프라면 MST의 간선 수는 N-1)가중치 합이 최소여야 함MST의 활용통신 네트워크 구축 (최소 비용으로 도시 연결)전력망 설계 (최소 비용으로 전선 연결)도로 네트워크 최적화이미지 처리, 군집화(Clustering) ..
1. 서로소 집합(Disjoint Set)이란?서로소 집합(Disjoint Set)은 겹치는 원소가 없는 집합들의 모임을 의미한다.서로소 집합의 핵심 연산서로소 집합을 다룰 때 핵심적으로 사용하는 연산은 다음과 같다.makeSet(x): 각각의 원소를 독립적인 집합으로 초기화findSet(x): 특정 원소 x가 속한 집합의 대표(루트) 찾기union(x, y): 두 개의 집합을 합치기서로소 집합의 활용서로소 집합은 유니온-파인드(Union-Find) 알고리즘을 사용하여 효율적으로 집합 연산을 수행할 수 있다.대표적인 활용 예시는 다음과 같다.네트워크 연결 확인 (컴퓨터 네트워크, 친구 관계)최소 신장 트리(MST, Kruskal's Algorithm)동일 집합 여부 확인 (서로소 판별)경로 압축(Path..
트리(Tree)란?트리는 계층적인 데이터 구조를 표현하는 자료구조이다. 비선형 자료구조로, 루트(Root)에서 시작하여 여러 개의 자식 노드(Child Node)를 가질 수 있다.트리의 특징사이클이 없는 연결 그래프 (Acyclic Graph)노드(Node)와 간선(Edge)으로 구성루트 노드(Root Node): 트리의 최상단 노드자식 노드(Child Node): 부모 노드(Parent Node)에 연결된 하위 노드들리프 노드(Leaf Node): 자식이 없는 노드깊이(Depth): 루트에서 특정 노드까지의 경로 길이높이(Height): 루트에서 가장 깊은 노드까지의 거리 이진 트리(Binary Tree)란?이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다.이진 트리의 종류포화 ..
과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.https://superohinsung.tistory.com/176 [DataStructure] 트리(Tree)트리란 자료구조에서 트리(Tree)는 계층적인 구조를 갖는 비선형 자료구조이다. 트리는 노드(Node)들로 구성되며, 이들 간에 부모-자식 관계가 있다. 최상위 노드를 루트(Root)라고 하고, 각 노드는 0superohinsung.tistory.com 그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다. BFS (Breadth-First Search)란?BFS는 시작 정점에서 가까운 정점부터 차례대로 탐색..
과거에 나는 DFS와 BFS에 대해서 간단하게 정리한 경험이 있다. 이번에는 다시 한번 더 공부겸 좀 더 많은 것들을 기록하고자 다시 한번 더 포스팅을 해보자.https://superohinsung.tistory.com/176 [DataStructure] 트리(Tree)트리란 자료구조에서 트리(Tree)는 계층적인 구조를 갖는 비선형 자료구조이다. 트리는 노드(Node)들로 구성되며, 이들 간에 부모-자식 관계가 있다. 최상위 노드를 루트(Root)라고 하고, 각 노드는 0superohinsung.tistory.com 그래프 탐색(Graph Traversal)은 그래프의 모든 정점을 방문하는 과정이다. DFS (Depth-First Search)란?DFS는 한 정점에서 시작하여 가능한 한 깊이 내려간 후..
부분집합이란?어떤 집합 S = {1, 2, 3}이 주어졌을 때, 이 집합에서 만들 수 있는 부분집합은 다음과 같다.{}{1}, {2}, {3}{1,2}, {1,3}, {2,3}{1,2,3}즉, 원소가 N개인 집합에서 만들 수 있는 부분집합의 개수는 2^N개이다.각 원소를 포함할지 말지를 결정하면 되므로 N개의 원소에 대해 각각 "선택" 또는 "비선택" (2가지 선택지)가 주어지기 때문이다. 재귀함수를 이용한 부분집합 with Javaimport java.io.BufferedReader;import java.io.InputStreamReader;// 부분집합: 재귀함수 버전public class SubSet { private static int N; private static int[] input; //..
1. 순열(Permutation)순열은 주어진 N개의 원소 중에서 R개를 뽑아 순서를 고려하여 나열하는 경우의 수를 의미한다.즉, N개의 요소에서 R개를 선택하여 나열하는 방법의 수이다.순열 구현 (Java, 재귀함수 이용)import java.util.Arrays;import java.util.Scanner;// 순열: 재귀함수 버전// 원소 개수, 뽑을 개수, 원소들 입력받기public class Permutation { private static int N; private static int R; private static boolean[] isSelected; // 원소 선택여부 체크배열 private static int[] numbers; // 하나의 경우를 담는 배열 private sta..
세그먼트 트리(Segment Tree)란 세그먼트 트리(Segment Tree)는 효율적으로 배열 또는 리스트와 같은 순차적인 데이터 구조에서 구간 쿼리(구간 검색 또는 구간 연산)를 수행하기 위한 자료구조입니다. 주로 구간 합, 구간 최솟값, 구간 최댓 값 등을 빠르게 계산하는데 사용됩니다. 세그먼트 트리는 트리 구조로 표현되며, 각 노드는 배열의 일부 구간에 대한 정보를 저장합니다. 일반적으로 이진 트리 형태를 가지며, 아래와 같은 구성요소를 가집니다. 루트 노드 : 배열 전체 구간에 대한 정보를 저장합니다. 각 내부 노드 : 두 자식 노드의 구간 정보를 합친 결과를 저장합니다. 이를 통해 트리를 아래로 내려가면서 구간 정보를 계산할 수 있습니다. 리프 노드 : 배열의 개별 원소를 나타냅니다. 세그먼..
