Development Palette

1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net package com.personal.w0824.n1717_집합의표현; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int [] parents; static int find(int a){ if(..

이전에 사용한 union-find 코드와 완전 동일 여기서는 그룹의 개수가 몇개인지가 핵심 구현 부분이였다. 즉, 대표자의 개수를 알아내는것 ! package com.swea.w0824.n7465_창용마을무리의개수; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; import java.util.StringTokenizer; public class Solution { static int N; static int [] parents; static void make() { for(int i=1; i

0 a b의 형태로 입력 --> a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력 a와 b는 n 이하의 자연수이며 같을 수도 있다. 1로 시작하는 입력에 대해서 같은 집합에 속해있다면 1을, 아니면 0을 순서대로 한줄에 연속하여 출력한다. package com.swea.w0824.n3289_서로소; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.ut..

서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들. 즉, 교집합이 없다. Union - Find 알고리즘은 대표자를 정해 특정 멤버가 대표하여 각 집합을 구분한다. Union - Find 알고리즘의 집합연산 세가지 Make - Set(x) : 각 원소를 대표자로 하는 집합 만들기 Find - Set(x) : x가 속한 그룹의 대표자 찾기 Union(x, y) : x가 속한 그룹과 y가 속한 그룹을 합치기.. 이때 Find - Set을 이용해 대표자를 찾아 비교하여 소속그룹인지 확인한다. 연산의 효율을 높이기 위한 방법 Rank를 이용한 Union 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장. 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class AdjMatrixTest { static int N; // 정점 개수 static boolean[][] adjMatrix; // 인접행렬 (가중치 없음) public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedRead..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class AdjListTest { static class Node{ int vertex; // 인접정점 인덱스 Node link; public Node(int vertex, Node link) { this.vertex = vertex; this.link = link; } @Override public String toString() { return "Node [vertex=..

package com.baekjoon.w0823.n1759_암호만들기; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int L; static int C; static char [] input; static char [] num; // a t c i s w // 모음 : a e i o u 중에 a i //서로 다른 L개..

dir로 위치가 정해지는 게 헷갈렸는데 객체로 좌표값을 지정해주니까 좌표값의 위치를 더 빨리 파악할 수 있다. 앞으로 자주 사용해야겠음~!! 거리를 구할 때 규칙이 있을 것 같아서 이것저것 그려보다가 찾았다@!! 동근이나 상점이 양 옆이나 같은 라인에 있을 때, 두 좌표의 차의 절대값의 합으로 계산하면 된다. 동근이나 상점이 서로 반대편에 있을 때, 두 가지 경우가 있다. 1. (0,0)을 지나는 방법 - 두 좌표의 합 (변수a) 2. (R,C)를 지나는 방법 - 변수 b 참고 package com.testex.t0830_IM.w0817.n2564_경비원; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre..