분류 전체보기108 백준 1717번 : 집합의 표현 문제 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 구현 방법 union-find 알고리즘을 통해 구현하였습니다. n만큼 집합을 생성하고 연산을 받아 0 a b이면 합집합으로 union(a, b) 를 통해 집합을 합쳐줍니다. 1 a b면 연결 되었는지 확인해야합니다. path competition을 통해 연산 시 부모를 루트 노드로 향하게 구현하였으므로 a의 부모, b의 부모를 찾아 같으면 연결 -> "YES" 출력.. 2021. 3. 21. 백준 1976번 : 여행 가자 문제 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 구현 방법 union-find로 구현해주었습니다. 도시의 수 만큼 root 배열인 parents 배열을 만들어주고 도시 집합을 생성합니다. 연결 정보를 받아와 1이면 union(x, y) 로 집합을 합쳐줍니다. 모든 연결이 끝난 후 여행 계획을 받아와 루트 노드를 찾아 같으면 연결되었으므로 "YES" 출력, 다르면 비연결이므로 "NO"를 출력해줍니다. 구현 코드 package BOJ.Gold; import.. 2021. 3. 21. Union-find 알고리즘 Union-find란? 서로소 집합 (Disjoint-set : 서로소 또는 상호배타 집합, 서로 중복 포함된 원소가 없는 집합) 을 표현할 때 사용하는 알고리즘 서로소 집합 연산 Make-Set(x) : x를 유일한 원소로 하는 집합 만드는 연산 Find-Set(x) : x의 대표자 (집합에 속한 하나의 특정 멤버) 값을 반환하는 연산 Union(x, y) : x집합을 y집합에 합치는 연산 트리 표현 - 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자 static void makeSet() { // 크기가 1인 단위집합을 만든다. for (int i=1;i 2021. 3. 21. 백준 11726번 : 2xn 타일링 문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 구현 방법 위의 계산을 통해 dp[N] = dp[N-2]*2 + dp[N-1] 임을 알 수 있습니다. 10007로 나눈 나머지를 출력해줘야 되기 때문에 dp에 값을 저장할 때부터 나눈 값을 저장해줍니다. 출력할 때 나누어 주면 수가 int 범위를 넘어서기 때문에 미리 저장하여 나눠줍니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOExce.. 2021. 3. 21. 이전 1 ··· 10 11 12 13 14 15 16 ··· 27 다음
