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; //..
Kotlin in Action을 스터디하며 정리한 내용입니다.저작권에 문제가 될 시, 글을 모두 내리겠습니다.제가 공부한 내용이 더 많은 분들에게도 도움이 되었으면 좋겠습니다. 부족한 부분은 댓글을 통해서 피드백을 주신다면 언제나 반영하겠습니다. 감사합니다.책에 대한 링크는 맨 아래에 있습니다.https://github.com/Kotlin-Android-Study-with-SSAFY/Kotlin_In_Action_1 GitHub - Kotlin-Android-Study-with-SSAFY/Kotlin_In_Action_1: SSAFY 13기 모바일 트랙 구미 5반 "코틀린 인 액션" 스SSAFY 13기 모바일 트랙 구미 5반 "코틀린 인 액션" 스터디(A). Contribute to Kotlin-Andr..
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..
문제https://www.acmicpc.net/problem/8111 어떻게 풀 것인가?우선 문제를 읽으면서 수를 보며 잠깐 수학개념에 대해서 생각을 하다가, "어? BFS문제로 풀릴거 같은데?" 라는 생각으로 접근하였다. 하지만 문제가 풀리지 않아서 다른 분의 풀이를 결국엔 참고할 수 밖에 없었다. 맨 아래에 참고했던 블로그들의 링크를 걸어 두었다. 그래도 내가 이해한 것을 기반으로 작성해보자. 모듈러 법칙을 활용한 BFS 접근법 정리:이 문제는 주어진 수 N 으로 나누어 떨어지는 0과 1로 이루어진 가장 작은 수를 찾는 문제다. 단순히 BFS로 숫자를 확장하는 것만 생각하면 해결하기 어렵지만, 모듈러 연산의 특성을 이용하면 효율적인 탐색이 가능하다. 모듈러 법칙 활용어떤 수 A 를 B 로 나눈 나머지..
문제https://www.acmicpc.net/problem/15683 어떻게 풀 것인가?CCTV 방향 탐색을 위한 순열 생성permutation(0, cctvList.size())을 호출하여 DFS 기반 순열 생성을 수행한다.각 CCTV는 최대 4가지 방향을 가질 수 있으므로, 모든 CCTV의 가능한 방향 조합을 만들어서 하나씩 테스트한다.모든 CCTV에 대해 방향이 결정되면, 원본 map을 copyMap에 복사한 후, 해당 조합으로 CCTV 감시를 수행한다.CCTV 감시 영역 설정direction(CCTV cctv, int d) 함수는 CCTV의 종류에 따라 감시 방향을 설정하는 역할을 한다.각 CCTV는 다음과 같이 감시할 방향을 결정한다:1번: 한 방향 감시2번: 서로 반대 방향 두 곳 감시3번:..
문제https://www.acmicpc.net/problem/17471 어떻게 풀 것인가?문제의 접근조차 어려워서 잠깐의 고민 끝에 결국엔 다른분의 풀이를 참고하였다. 오늘의 포스팅은 기억을 남기기 위한 용도라고 생각하며 작성하였다. 문제의 접근의 경우 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현)나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함)두 지역의 차이 값 중에서 최소값을 찾아준다.좀 더 풀어서 작성해보자. 먼저, 입력을 통해 각 지역의 인구 수와 연결된 지역 정보를 받아 저장한다. 이후, 선거구를 나누기 위해 각 지역이 속할 선거구를 정하는 모든 경우의 수를 탐색한다. 이를 위해 깊이 우선 탐색(DFS)을 사용하며, 각 지역을 두 개의 ..
Kotlin in Action을 스터디하며 정리한 내용입니다.저작권에 문제가 될 시, 글을 모두 내리겠습니다.제가 공부한 내용이 더 많은 분들에게도 도움이 되었으면 좋겠습니다. 부족한 부분은 댓글을 통해서 피드백을 주신다면 언제나 반영하겠습니다. 감사합니다.책에 대한 링크는 맨 아래에 있습니다.https://github.com/Kotlin-Android-Study-with-SSAFY/Kotlin_In_Action_1 GitHub - Kotlin-Android-Study-with-SSAFY/Kotlin_In_Action_1: SSAFY 13기 모바일 트랙 구미 5반 "코틀린 인 액션" 스SSAFY 13기 모바일 트랙 구미 5반 "코틀린 인 액션" 스터디(A). Contribute to Kotlin-Andr..
