정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B www.acmicpc.net 1. 풀이 N이 10만, 쿼리 개수가 10만이라 한 쿼리당 log N이 걸려야 한다. [PS/LCA] - [BOJ] ..

0. 문제 주소 https://www.acmicpc.net/problem/1626 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다. 정점 번호는 1보다 크거나 같고, V보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 *** 첫 다이아 문제 *** 기본 아이디어는 다음과 같다. 0. 크루스칼 알고리즘을 이용해 MST를 만든다. 기존 그래프와 별도로 만들어줄 것이고, 사용하지 않은 간선들은 notused_PQ(min heap)에 따로 ..

0. 문제 주소 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1

0. 문제 주소 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. 이때에는 한 정수만 주어지며, B는 꺼낼 사탕의 순위를 의미한다. 이 경우 사탕상자에서 한 개의 사탕이 꺼내지게 된다. 또, A가 2인 경우는 사탕을 넣는 경우이다. 이때에는 두 정수가 주어지는데, B는 넣을 사탕의 맛을 나타내는 정수이고 www.acmicpc.net 1. 풀이 세그트리를 이용해서 맛의 좋고 나쁨을 나타내는 1부터 100만까지의 수에 대해서, 구간 합을 저장하는 세그트리..

0. 문제 주소 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 풀이 인덱스 트리를 이용하여 풀어보려고도 했는데,,, 재귀로 하면 TLE가 난다. 비재귀 세그 트리를 써야 한다는데 나중에 알아봐야겠다. 도저히 모르겠어서 찾아본 결과 deque을 이용한 O(N) 풀이를 찾았다. 슬라이딩 윈도우 기법을 사용하되, 가지고 갈 필요가 없는 원소들은 바로바로 빼 줄 것이다. 0. pair를 이용하여 각 원소에 순서를..

0. 문제 주소 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 문제 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다. 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 www.acmicpc.net 1. 풀이 알고리즘 분류가 "이분 탐색"이라고 되어 있는 것을 보고 처음에 생각난 풀이는 다음과 같다. 0. 집들과..

0. 문제 주소 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 1. 풀이 먼저 A와 B 배열에 대해, 가능한 모든 부배열의 합을 구해 놓는다. 우리가 원하는 상황은, A의 부배열 합 + B의 부배열 합 = T가 되는 상황이다. A의 부배열 ..

0. 문제 주소 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 1. 풀이 inversion 개수를 구하는 문제. 강사님이 merge sort를 구현하면서 inversion을 구할 수 있다고 하셨고, 이해도 갔지만 구현이 어려울 것 같았다. 그래서 ICPC를 준비하며 봤던 내용으로 인덱스 트리 / 펜윅 트리를 이..

0. 문제 주소 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 풀이 투 포인터 문제. 왼쪽과 오른쪽 포인터들을 각각 어느 조건에서 움직여야 하는지, 종결 조건은 무엇인지 순서가 항상 헷갈렸다. 생각해볼 점은 다음과 같다. 0. 왼쪽 포인터를 L, 오른쪽 포인터를 R이라 하자. 1. 주어진 배열의 수들은 모두 자연수이다. 2. 1.의 이유로 R을 오른쪽으로 옮기면, L과 R이 나타내는 구간합은 무조건 커진다. 3..

0. 문제 주소 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 풀이 검색해보고 신세계였던 문제. 'level 별로 보는 BFS'라는데 이 말만 들으면 헷갈리니까 예시를 들어보자. 우선 문제에선 K번 바꾸는 동안의 최댓값이 아니라, 정확히 K번을 바꾼 후의 최댓값을 묻고 있다. A라는 숫자에서 i번째 swap을 통해 B를 얻었다고 하자. 앞으로 K-i번의 swap을 더 해야 한다. 앞으로 해야 할 K-i번의 swap의 모든 결과값들 중에, B가 나오면 안 될까? 그렇지 않다. 예를 들어, sample c..

0. 문제 주소 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 1. 풀이 약간 내리막길 문제랑 비슷한 느낌이 들었다. 맨 처음엔 칸 별로 연결관계를 만들어 BFS를 돌리려고 했으나... 멍청한 생각이었다. DFS + DP의 풀이를 사용한다. top-down은 어렵다 ㅠ 주의해야 할 점은 cycle의 유무이다. [PS/BFS & DFS] - [BOJ] 9466: 텀 프로젝트에서 DFS를 ..

0. 문제 주소 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다. www.acmicpc.net 1. 풀이 백트래킹이라고 하긴 했지만 가지치기는 안 해서 사실상 완전 탐색 문제 처음에 시간 초과가 났는데, 1. 모든 단어에 포함되어 있는 'a', 'n', 't', 'i', 'c'의 5글자를 빼주지 않아서 2. 조합 경우의 수를 재귀적으로 구할 때 vector를 인자로..

0. 문제 주소 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 1. 풀이 BFS 두 번 돌리는 문제. 잠깐 " 물 한 번 / 고슴도치 한 번 " 으로 해 볼까? 하다가 그럴 필요가 없는 ..

0. 문제 주소 https://www.acmicpc.net/problem/3425 3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하 www.acmicpc.net 1. 풀이 진짜 극혐 DIV와 MOD 연산에서 부호 처리에 관해 주저리주저리 써놓았는데, c++에서 / 과 % 연산자가 알..

0. 문제 주소 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1. 풀이 나쁜 수열을 어떻게 판별할까 고민했던 문제. 확실히 c++로 문자열을 처리하는 부분이 약한 걸 느꼈다. 마지막에 새로 추가하는 숫자를 포함하는 부분 수열만 체크할 것이고, 이 경우 체크해야 할 인접한 부분 수열의 길이는 1부터 (현재 문자열의 길이) / 2 까지 일 것이다. 그렇기에 부분 문자열의 길이를 i라 하고, 현재 문자열의 길이를 N이라고 한다면 비교해야 할 두 부분 수열은 ..

0. 문제 주소 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 9084: 동전 참고 개수의 제한에 주의할 필요가 있다. [PS/DP] - [BO..

0. 문제 주소 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 소문자를 대문자로 써놔서 근데 또 돌아가서 시간만 날린 문제...지만 좋은 문제 가장 먼저 필요한 건 i 개의 a와 j 개의 z로 만들 수 있는 단어의 개수를 저장할 2차원 dp 테이블이다. 단순하게 (i+j) ! / ( i ! ) ( j ! ) 으로 계산할 수 있지만 당연히 오버플로우가 나기 때문에, dp를 이용한다. K의 값이 10억 이하이므로, 그 이상은 오버플로우 처리를 위해 값이 10억을 초과하면 10억 + ..

0. 문제 주소 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 1. 풀이 교점이 생기면 안 된단다. 그냥 LIS 문제다. LIS 풀이는 여러가지가 있지만, 이 문제에선 N 제한이 40000이므로 dp, 즉 O(N^2)로는 풀 수 없다. lower_bound를 사용하면 O(n log n)으로 쉽게 풀 수 있다. 먼저 빈 배열 d를 설정해두고, 기존 배열..

0. 문제 주소 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하 www.acmicpc.net 1. 풀이 대표적인 tree DP 문제. 먼저 연결 관계로 vector 배열 child를 이용해 트리를 만들고..

0. 문제 주소 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 11049: 행렬 곱셈 순서와 똑같은 기법을 사용하는 dp 문제. 마찬가지..

0. 문제 주소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 1. 풀이 2차원 배열을 이용하여 모든 구간별 정보를 메모이제이션 하는 dp 문제. 다시 말해서, i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장할 것이기 때문에, 이 정보들을 이용하기 위해선 곱셈 형태를 큰 부분 두 개로 나누어야 한다. A, B, C, D 4개의 행렬이 있다고 가정해 보자. 메모이제이션을 통해 A ~ C , 그리고 B ~ D ..

0. 문제 주소 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 문제에 있는 예시는 M이 너무 크므로, 다음과 같은 예시를 들어보자. 동전 종류 : 2, 4, 5 만들어야 하는 금액 : 10 기본 개념은, 첫 번째 ~ i 번째 까지의 동전을 사용했을 때,..

0. 문제 주소 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 문제에서 예시로 준 input을 사용하자. input :: ACAYKP CAPCAK 표로 이해하면 편하다. 다음과 같이 2차원 dp 배열을 설계한다. 0 1 2 3 4 5 6 C A P C A K 0 0 0 0 0 0 0 0 1 A 0 2 C 0 3 A 0 4 Y 0 5 K 0 6 P 0 ACAYKP를 str1, CAPCAK를..

0. 문제 주소 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 1. 풀이 이게 왜 골드 1이지??? 기존 문제들과 달랐던 점은 다음과 같다. 지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. dp 배열은 3차원으로 짰는데, dp[i][j][0] = (i, j) 기준 위쪽, 왼쪽에서 (i, j)로 올 때 가장 큰 값을 저장 dp[i][j][1] = (i, j)..

0. 문제 주소 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 1. 풀이 [PS] - [BOJ] 9466: 텀 프로젝트 랑 똑같은 문제. 윗줄에서 적절히 숫자들을 골랐을 때, 고른 ..

0. 문제 주소 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의 www.acmicpc.net 1. 풀이 사실 DFS 카테고리에서 고른게 아니었으면 조금 헤맸을 수도 있었을 문제. 배열은 총 3개를 사..

0. 문제 주소 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북 www.acmicpc.net 1. 풀이 귀찮지만 실수 없이 코드 짜는 연습 하기 좋은 문제. 총 4개의 배열을 사용한다. int grid[MAX]..

0. 문제 주소 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 1. 풀이 DFS로 사이클 구하는 연습 용으로 풀어 본 문제. 사이클이 발생했냐를 판단하는 기준으로 두 가지 배열을 ..

0. 문제 주소 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 1. 풀이 BFS & DFS 카테고리를 밀다가 본 문제. 보자마자 union-find를 생각하고 코드까지 짜다가 문제..