MuviSsum

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제: 사이클이 생긴다면 그 즉시, 해당 번호를 출력하라. 문제 이해하기!! 처음에는 이게 무슨 문젠가 싶었어요. 일단 그래프 문젠데... 연결해서 사이클이면 어떻게 해야하지 라고 생각했었는데 아니;; 그래프 문젠줄알고 들어가서 풀었는데 분리집합이더라구요. 들어오는 것들 union으로 싹 다 넣어서 부분 집합을 통일시키면 되는데, 들어오기 전에 둘의 부모가 같아서 이미 해당 부분집합에 들어가 있는 두 숫자..

www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제: 0이면 해당 수가 들어가 있는 집합 둘을 합치고 1이면 둘이 같은 집합인지 확인해라. 문제 이해하기!! 이 문제는 그냥 유니온 파인드라고 광고를 하고 만든 문제인 것 같습니다. 0일 때, 두 집합을 합치고, 1일 때, find() 함수로 둘의 부모를 확인하면 됩니다. 문제를 풀 때, 한 번 틀렸는데... 최대재귀깊이를 생각 못 해서 ㅠㅠ 근데 요즘 백준에서 왜 틀..

www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 문제: 준석이가 돈을 내고 친구를 구하는데, 친구의 친구도 친구가 된다. 최소비용으로 모든 친구를 사겨라. 요즘 최소 스패닝 트리에 대해 다시 리마인드하는 차에 크루스칼 알고리즘의 부모 격인 유니온 파인드 문제들을 풀어보고 있습니다. 거기서도 대표 문제 격인 "친구비" 문제입니다. 사실 문제 이해하는 단계를 지나 알고리즘 분류를 통해 들어갔기 때문에 이해 단계를 생..