https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 이것 또한 유니온파인드 응용문제이나, 기초가 탄탄하다면 쉽게 풀 수 있는 문제이다. int[] parent 배열로 그룹번호를 관리해주고 int[] min 배열로 해당 그룹의 최소 친구비를 관리해주면 된다. import java.io.*; import java.util.*; public class Main { private static int[] par..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온파인드 응용 문제이다. boolean[] know 배열을 이용하여 진실을 아는 그룹을 체크해주면 된다. 유니온파인드 기초만 탄탄하다면 응용하기 어렵지 않은 문제 import java.io.*; import java.util.*; public class Main { private static int[] parent; private static boolean[] know; public static void..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 시뮬레이션 + BFS 문제이다. BFS에 익숙하다면 시간 단위로 거리가 가장 가까운 물고기를 찾는 것은 쉽게 해결할 수 있을 것이다. 다만 문제에서 한 가지 골치아팠던 점은 거리가 똑같은 물고기가 여러 마리인 경우에 위쪽에 있는>오른쪽에 있는 물고기 순으로 먹어야한다는 것이다. 그래서 해당 시간에서 먹을 수 있는 물고기가 있다면 pq에 담아주었다. // 움직일 수 있으면 일단 큐에 담는다...

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 코테 기출에 시뮬레이션 문제이다보니 할게 아주아주 많은 정말 귀찮은 문제였다. 하지만 함수를 만들어서 절차에 따라서 진행해주니 해결할 수 있었다. 해야 할 일 1. 먼지 확산시키기 2. 공기청정기로 공기 이동시키기 크게는 요 두 가지밖에 없지만, 확산되서 더해질 먼지와 기존의 먼지를 별개로 구분해야했기에 이 부분이 조금 귀찮았다. 그래서 확산시킬 먼지는 Queue에 담고, Queue에서 먼지 정..

https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 효율성의 함정에 빠져서 어떻게 브루트포스로 안풀고 해결하지 고민하다가 오래걸린 문제,,, 그냥 가능한 경로를 일일이 해보면 되는 문제였다 😓 1. 욱제가 상/하/좌/우/대각선4방향/그대로 총 9 방향으로 움직이거나 멈춰있을 수 있습니다. 현재 있는 칸과 움직일 칸 모두에 벽이 있으면 안됩니다. // 현재의 칸(p.i,p.j)에서 9방향으로 돌려가며 ni와 nj를 찾는다. int ni =..

이렇게 연결되있으면 못찾음 // 프림 boolean[] visit = new boolean[n]; double[] minEdge = new double[n]; Arrays.fill(minEdge, Double.MAX_VALUE); int v = 0; // 시작점: 0 visit[0] = true; int cnt = 0; double ans = 0; while (cnt < n - 1) { double dist = Double.MAX_VALUE; int minNode = v; for (int i = 0; i < n; i++) { if (visit[i] || adj[v][i] == 0) continue; // 나와 그 점과의 거리가 지금보다 작아야돼 if (adj[v][i] < dist) { dist = ad..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션 문제이다. 주어진 순서대로 찹찹 구현하면 된다. 시뮬레이션 치고 생각할게 많아서 좀 복잡했다. CCTV의 최대 개수가 8개이기때문에, CCTV의 모든 방향의 경우의 수를 탐색한다고 하더라도 4^8 = 65만 맵의 크기도 최대 64이기때문에 브루트 포스로 찾아도 시간은 충분하다고 본다. *구현 순서* 1. CCTV의 위치를 찾아서 저장한다. 2. CCTV의 가능한 방향을 계산한..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 간단한 분할정복 문제이다. N이 무조건 2의 거듭제곱 꼴로 주어진다. 문제 이름 쿼드트리 그대로 네모를 사등분하여 생각해주면 된다. 네모의 모든 칸이 1또는 0으로 채워져있으면 압축 가능하기때문에, 이 조건을 넣어서 String값을 return해주면 된다. 비트 시프팅을 이용하여 아주아주 간단한 소스코드로 풀 수 있다. import java.io.*; public class Main ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. 문제 풀이 떠오르는 풀이는 간단합니다. (조를 만들지 못하는 학생을 탈락했다고 표현) 인덱스 순서대로 진행하고, 현재 배열값이 가르키는 학생 번호로 이동해서 조를 짤 수 없으면 탈락된 학생들의 숫자를 더해주고, 하나의 사이클이 만들어졌다면 탈락하는 학생들이 없다는 이야기입니다. 사이클 여부는 맨 처음 학생의 번호와 비교했습니다. boolean[] visit배열을 이용하여 방문한 학생을 중복해서 방..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제도 단순하고, 난이도에 비해서 쉽게 푼 것 같다. 풀이 N자리 숫자가 주어졌을 때 가장 큰 수를 만들려면 앞자리 숫자를 가장 크게 만들어야 할 것이다. 그러면 앞에 숫자부터 비교해서 1. 다음자리 숫자가 나보다 큰 경우 && 아직 제거해야할 자릿수가 남은 경우 나를 지우고 다음숫자를 이어붙여준다. (1) 예를 들어 476127과 같은 경우 4 < 7이므로 4를 제거해야 함 (2) 76127 에서는 1 < 2 이므로 1을 제거 (3) 7627 에서는 2= c) break;..