Algorithm2 [BOJ 13398] 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위 문제는 연속합을 구하는 문제를 조금 바꾸어서 풀 수 있다. dp배열을 한 개를 제거했을 때, 제거하지 않았을 때로 나누어서 문제를 풀면 된다. dp[i][0] = 한 개를 제거하지 않고 i번째까지의 가장 큰 연속합 dp[i][1] = 한 개를 제거하고 i번째까지의 가장 큰 연속합 이렇게 나누어서 풀면된다. 제거하지 않고 구하는 건 max(0, dp[i - 1][0]) + a[i] (a[i]는 i번.. 2020. 4. 17. 유니온-파인드(Union-Find), 서로소 집합(Disjoint Set) Union Find와 Disjoint Set은 동일한 의미를 가지며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다. 트리 형태로 구현되며, 보통 자신의 root 노드를 집합을 구분하는 ID처럼 사용된다. 이 자료구조는 두 가지 연산을 지원한다. 1. find(p): p의 root 노드의 값을 가져옴 2. union(p, q): p와 q의 집합을 합친다. (코드 구성 시에는 union이라는 예약어가 있어 merge로 대체) 맨 처음에는 모든 노드가 자기 스스로를 root 노드로 가지게 된다. find 함수는 현재 자기의 parent 노드가 자신이면 자기를 반환하고, 아니면 자신의 parent 노드의 parent노드를 반환한다. 이러한 방식으로 자신의 root 노드를 찾게 된다. union.. 2020. 4. 14. 이전 1 다음
