[백준 16202] MST 게임
문제 16202번: MST 게임 16202번: MST 게임 첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다. 두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있 www.acmicpc.net 풀이 문제 이름에도 나와 있듯 MST(최소 신장 트리)를 사용하는 문제이다. 문제에서 제시한 MST의 조건은, 스패닝 트리를 구성하는 간선의 개수는 N-1개이다. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다. 이다. 주어진 그래프에서 MST 값을 구하는 문제인데, 주의할 점은 턴마다 최소..
서로소 집합 : Disjoint Set(Union-Find)
개념 서로소 집합 자료구조, Disjoint Set, Union-Find 등의 이름으로 불린다. 서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계다. 즉, Disjoint Set은 공통되는 원소를 처리하기 위한 자료구조라 할 수 있다. Disjoint Set은 Union, Find라는 두가지 연산을 가진다. Union : 원소를 하나의 집합으로 합친다. Find : 원소가 속한 집합이 어떤 집합인지 찾는다. 동작과정 조건 원소의 갯수가 1~6이 있고 아래와 같이 원소를 합친다. 처리할 연산 → (1, 2), (2, 3), (3, 4), (5, 6) 구현 원소의 갯수만큼 배열을 만들고 해당 배열은 자기 자신을 가리키는 각각의 집합으로 초기화한다. union 메서드 public void union(in..
[백준 14002] 가장 긴 증가하는 부분 수열4
문제 14002번: 가장 긴 증가하는 부분 수열 4 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이 문제는 수열이 주어질 때 가장 긴 증가하는 부분수열의 길이와 요소들을 순차적으로 출력하는 문제이다. LIS와 Stack의 개념을 적용해 풀이해보자. LIS(Longest Increasing Subsequence) LIS의 약어를 해석해보면 최장 증가 부분 수열이다. 이것은 문제가 요구하는 수열을 의미하는 용어임을 알 수 있..
