본문 바로가기

개발 관련 공부/알고리즘28

유니온 파인드 최근에 졸업 시험과 기업 코테를 포함하여 여러번 코테를 쳤다. 그중에서 n의 크기가 300,000으로, 아무리 봐도 최소 nlogn 안쪽으로 풀어야 할 것 같은데 완탐 풀이법밖에 생각나지 않는 문제들이 2개 있었다. 그들의 공통점은 union find로 풀어야 하는 문제였다는 것이었다. 첫번째 문제를 만났을 때 유니온 파인드를 공부했다면 다른 문제는 풀 수 있었을지도 모르는데... 역시 모르는게 생기면 공부를 바로바로 해야 한다. 유니온 파인드에 대하여 유니온 파인드의 다른 이름은 서로소 집합이다. 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지 확인할 수 있다는 말과 같다. 그렇기 때문에 union-find라고 부른다. 기본 유형은 위 그래프의 연결 관.. 2022. 9. 16.
백준 11725 트리의 부모 찾기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int parents []; static ArrayList list []; public static void main(String[] args) { try{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); //arrayList 한 원소를 배열로... 배열의 한 원소가 어레이리스트인듯 list =new ArrayList [n+1]; for(int i=0;i 2021. 8. 26.
백준 1697 숨바꼭질 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); //수빈의 위치 int k=sc.nextInt(); //동생의 위치 boolean visited []=new boolean [100001]; Arrays.fill(visited, false); visited[n]=true; //걸음수를 넣는 배열 int status[]=new int [100001]; status[0]=n; Queue q =new Li.. 2021. 8. 25.
백준 7569 토마토2 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static int nx []= {1,-1,0,0,0,0}; public static int ny []= {0,0,-1,1,0,0}; public static int nz []= {0,0,0,0,-1,1}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int h=sc.nextInt(); int[][][] arr = new int[m][n][h]; .. 2021. 8. 24.
백준 7576 토마토 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static int nx []= {1,-1,0,0}; public static int ny []= {0,0,-1,1}; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m=sc.nextInt(); int n=sc.nextInt(); int arr [][]=new int [m+2][n+2]; int arr2 [][]=new int [m+2][n+2]; boolean check [][]=new boolean[m+2][.. 2021. 8. 23.
백준 1302 베스트셀러 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); HashMap map =new HashMap(); String arr []=new String[n]; for(int i=0;i 2021. 8. 20.
반응형

티스토리툴바