CNU 학습 동아리/2020 동계 학습 동아리7 2020 동계 학습 동아리_3회차_2020-02-07(금) Union-find(Disjoint-set) - Disjoint set : 서로 중복되지 않는 집합(서로소 집합) - Union-find : disjoint set을 표현하기 위해 사용하는 알고리즘 Union-find의 메소드 - find(x) : x가 속한 집합의 대표값을 반환한다. - union(x,y) : x가 속한 집합과 y가 속한 집합을 합친다. 구현 방법 1. 배열 - find(x) : O(1) - union(x,y) : O(N) 2. 트리 - find(x) : O(트리의 높이) - union(x,y) : < O(N) 관련 알고리즘 문제 https://www.acmicpc.net/problem/tag/Disjoint-set Disjoint-set - 1 페이지 www.acmicpc.net 초심.. 2020. 2. 7. 2020 동계 학습 동아리_2회차_2020-02-04(화) 목표 > 카카오 코드 페스티벌 2018 예선 B번 문제 풀기 https://www.acmicpc.net/problem/15954 15954번: 인형들 첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째까지의 인형을 선택하는 경우에도 값은 같다. www.acmicpc.net 결과 해결 방법 > 항상 그렇듯이 카카오 문제는 이해를 하는 것이 가장 어려운 것 같다. > 입력으로 들어오는 N은 인형들의 수, K는 골라야 하는 인형들의 수, 두 번째 줄에 들어오는 배열은 인형들을 선호하는 사람들의 수이다. > 쉽게 말해서 N개의 인형들 중에 K개 이상의 연속된 인형을 뽑아서(.. 2020. 2. 4. 2020 동계 학습 동아리_1회차_2020-02-03(월) 목표 > 카카오 코드 페스티벌 2018 예선 A번 문제 풀기 https://www.acmicpc.net/problem/15953 15953번: 상금 헌터 첫 번째 줄에 제이지가 상상력을 발휘하여 가정한 횟수 T(1 ≤ T ≤ 1,000)가 주어진다. 다음 T개 줄에는 한 줄에 하나씩 제이지가 해본 가정에 대한 정보가 주어진다. 각 줄에는 두 개의 음이 아닌 정수 a(0 ≤ a ≤ 100)와 b(0 ≤ b ≤ 64)가 공백 하나를 사이로 두고 주어진다. www.acmicpc.net 결과 그 동안 사용하지 않고 있던 C언어로 기본적인 배열 사용법에 대해 공부하고 풀어보았다. 코드 더보기 #include int main() { int N; int a, b; int prize = 0; int first[] = .. 2020. 2. 3. 이전 1 2 다음
