매일 조금씩

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 풀이 union-fin..

문제 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 MST 만드는 문제로 보여서 크루스컬 알고리즘으로 풀었다. 가중치가 적은 간선부터 사이클이 만들어지지 않을 경우, 연결해 나간다. 소스코드 import java.util.*; class Edge implements Comparable{ int nodeA; int nodeB; int weight; public Edge(int nodeA, int nodeB, int weight){ this.nodeA = nodeA; this.nodeB = nodeB; ..

#문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #풀이 Kruscal 알고리즘을 이용하여 문제를 풀었다. 두 정점 간의 비용이 주어지지 않기 때문에 간선 정보를 직접 만들어줘야 한다. 이중 For문으로 모든 정점을 순회하면서 쌍을 만들어 Edge를 생성해주었고 이때 distance를 계산해서 가지고 있게 했다. (다행히 별의 개수가 100개로 제한되어 있기 때문에 시간 초과 문제는 없었다.) 그리고 EdgeList를 distance 오름차..

#문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #풀이 M개의 선분이 주어지고 Cycle이 발생하는 순간의 차례를 리턴하는 문제이다. Union-find 기법의 대표적인 문제이다. MakeSet(): parent, rank 초기값 설정 parent는 자기 자신, rank는 0으로 초기화 Find(a): 원소 a의 parent node (root node)를 리턴 path-compression 기법으로 중간 가지를 없애고 parent..