알고리즘/문제풀이 (78) 썸네일형 리스트형 [백준] 1707. 이분 그래프 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 문제를 풀기 위해서 이분 그래프의 개념을 확실하게 알고가야 합니다. 그래프를 두 그룹으로 나누어서 각 그룹이 서로 연결되어 있지 않다.. [SWEA] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.StringTokenizer; /* * 1244_최대상금_Greedy * Greedy : 코드 간단, 속도 빠름 * 가설이 틀리면 답을 구하지 못할 수 있다. 103ms * * 완탐 => 가지치기 144ms * */ // Z35_Solution_SWEA_1244_최대상금_Greedy public class Solutio.. [백준] 13460. 구슬 탈출 2 https://www.acmicpc.net/problem/13460 불러오는 중입니다... 저는 처음에 예제 7번이 이해가 잘 가지 않았습니다. 여기에서 왼쪽으로 기울이게 되면 R이 먼저 빠지는데 정답은 -1이었습니다. 다시 문제를 읽어보니까 한번 보드를 기울이게 되면 R이 먼저 O으로 빠지지만 B도 역시 O으로 빠지기 때문에 -1이 출력되는 것입니다. 위 같은 이유때문에 빨간구슬과 파란구슬의 좌표를 입력받고 재귀적으로 모든 방향으로 기울여봐야하는데 빨간구슬이 앞에있는지 파란구슬이 앞에 있는지 판단하는 것이 까다로웠습니다. 빨간 구슬과 파란 구슬이 같은 선상에 있을 경우에 기울였을 때 같은 좌표로 가기 때문입니다. 이 점에서 해결을 하지 못해서 다른 블로그를 통해서 아이디어를 얻었는데, 방법은 두 구슬이.. [SWEA] 3289. 서로소 집합 import java.util.ArrayList; import java.util.Scanner; public class Solution { static int n, m; static int[] p; static int[] rank; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc=1; tc [SWEA] 1258. 행렬찾기 [ 문제 풀이 ] 1. DFS를 하면서 화학 물질이 들어있는 용기들의 좌표를 visited 에 true 로 표시해줍니다. 2. 표시했으면 용기들의 가로세로 길이를 구해야하기 때문에 다시 반복문을 처음부터 돌면서 visited 가 true인 좌표에서 좌우로 visited 가 true 인 곳을 r과 c로 체크하여 가로 세로 길이를 구하고 getLen 이라는 2차원 boolean 배열에 표시합니다. 그 이유는 다음 좌표가 이미 용기로 정해져 계산 될 경우 그 자리는 계산하지 않아도 된다는 것을 표시하기 위함입니다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Solution { st.. [백준] 17471. 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net N 개의 구역이 있으면 1 ~ N-1 개의 뽑을 수 있는 모든 구역을 뽑아서 두 가지를 판단 합니다. ① 뽑힌 선거구가 연결 되어 있는지 ② 뽑힌 선거구를 제외한 나머지 선거구들이 연결 돼 있는지 두 가지 조건을 만족하면 각 선거구들의 포함된 인구수를 구해서 차이값을 계속 비교하면서 최소를 구합니다. 제가 처음에 썻던 조합코드는 중복 때문에 시간초과가 나왔는데, 제가 정리했던 https://daily-life-of-b.. [백준] 17135. 캐슬 디펜스 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제에서 나온 순서대로 진행하면 되는 시뮬레이션 문제입니다. 문제를 풀면서 주의할 점이 2가지 있습니다. (1) 궁수 3명을 배치할 수 있는 모든 자리에 배치하여 그 때 마다 게임을 진행 해 보면서 제거할 수 있는 적의 최대 수를 계산하는 것 (2) 궁수가 공격하는 적은 거리가 D 이하인 적 중에서 가장 가까운 적인데, 그러한 적이 여럿일 경우에 가장 왼쪽에 있는 적을 공격하며, 같은 적이 여러 궁수에게 공.. [백준] 3109. 빵집 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵 www.acmicpc.net 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 문제입니다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열.. 이전 1 2 3 4 5 ··· 10 다음
