전공공부

설명다리 두개를 단순히 연결해서 N - 2개의 다리 상태에서 N - 1의 다리 상태로 모두 이어 질 수 있는 방안을 출력하면 되는 문제입니다. 단순히 분리집합을 이용해서 합집합끼리 묶고 남은 root 위치의 위치 값은 나눠진 것이니 이것을 연결 해줍니다. 위 설명이 바로 이해가 되지 않는다면 disjoint_set 자체에 대해서 조금 더 공부하시면 바로 이해 하기가 쉽습니다.   코드 package BOJ.disjoint_set;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_17352 { static int[] parent; public s..

설명분리집합 문제 였습니다. BOJ_18116과 같은 방식의 풀이로 진행하였으며 이때 문제 함정이 F  코드package BOJ.disjoint_set;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.StringTokenizer;public class BOJ_4195 { static int[] parent; static int[] size; static Map friendMap; public static void main(String[] args) throws Exception{ BufferedR..

설명우선 코드 자체는 Union-find를 활용하였다. 그 이유는 문제 설명 중 ( 부품 11과 부품 22가 로봇 A의 부품이라고 알고 있는 경우, robot(11)은 로봇 A를 의미하고, robot(22)도 로봇 A를 의미한다. ) 이와 같이 같은 집합의 로봇끼리는 같은 로봇으로 참고 하기 때문이고 그렇다고 해서 전체 집합의 로봇 부품들이 모든 같은 로봇을 참조하지는 않기 때문에 합집합 끼리 묶어 줄 수 있는 것이 필요하였기 때문이다. 다만, 10^6으로 parent 배열이 N + 1개를 의미하지 않기 때문에 root에 따른 동일한 부품 탐색 시 꽤나 탐색 범위가 커질 수 있다. 10^6 * 10^6과 같은 최악의 경우의 수가 나올 수 있기 때문에 단순히 for문으로 짜면 처음부터 끝까지 모두 탐색해서..

설명단순히 분리집합을 구현하여서 해당 위치가 같은 합집합에 속하는지 판단하는 것인데 이를 플로이드 와셜과 개념적으로 흔들리면 플로이드 와셜로 접근 할 수 있습니다. 다만, 해당 문제는 분리집합을 사용하여 N개 이상의 위치에 대해서 해당 위치가 처음 골라진 root 위치와 같아야 같은 곳을 통해서 지나 갈 수 있으므로 이를 모든 케이스에 대해서 다 점검하기에 단순히 1 -> N 어디로 간다의 로직을 짜는 플로이드 와셜과는 확실하게 다른 문제입니다. 코드package BOJ.disjoint_set;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;impor..

설명말 그대로 1사분면 2사분면 3사분면 4사분면을 나눠서 정복하는 방법입니다. 재귀 함수를 사용하기 때문에 적절히 리턴 코드를 의식해서 코드를 짜면 되고 사각형 탐색 시 모든 컬러가 같은 경우가 아닌 사각형을 탐색 했을때는 그 사각형의 내부를 탐색하는 식으로 코드를 작성하면 됩니다. 코드package BOJ.Divide;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_2630 { static int black = 0; static int white = 0; static int[][] map; public static void ma..

설명각 행렬별로 직사각형 형태의 PrefixSum을 구한 배열을 가지고 구할 크기의 직사각형을 이전 직사각형 형태로 만들어서 빼는 작업을 수행했습니다. 코드를 시각화 하자면 아래 그림과 같이 검은 직사각형 형태들로 내가 구하고 싶은 행렬인 빨간색 직사각형을 구하는 방식을 진행합니다. 사실 난이도에 비해서는 쉬운 문제였습니다. 별다른 기법이 필요한 것은 아니고 일반적인 구현 문제와 비슷합니다.    코드package BOJ.prefix_sum;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Strin..

설명간단히 누적합을 떠올려서 풀 수 있었던 문제입니다. 일일이 문제 조건을 카운트한다면 시간 초과가 날 것이 뻔했기 때문에 우선 문제 조건 중 각 원소들의 행의 합과 각 원소들의 열의 합을 구한다는 것에 포커스를 맞춰 접근했습니다. 행 누적합 배열 열 누적합 배열을 각각 두고 각 행 또는 열의 크기 만큼 각 배열에 V 값을 더해주되 열 배열일때는 행의 크기만큼 v를 곱해서 누적하고 반대로 행 배열일때는 열의 크기 만큼 v를 곱해서 누적하는 배열을 만들어 그대로 출력하였습니다. 코드package BOJ.prefix_sum;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java..

설명최대 N,Q가 100000인 건으로 일일이 다 체크하면 무조건 시간 초과가 나는 문제였습니다. 따라서, 누적합을 활용하여 문제를 풀었습니다. for N문으로 한 번에 누적된 케이스들의 값을 계속 끌고 가면서 그 사이에 위치한 사이 값이면 해당 누적합의 차이 만큼 빼서 사이에 얼마나 다음 케이스가 큰 케이스인지 체크해 푼 문제 입니다. 코드package BOJ.prefix_sum;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayList;import java.util.List;import ..