문제 개요 세로줄과 가로줄의 문제의 조건을 만족하는 경사로의 개수를 찾는 문제입니다. 문제 접근 구현문제입니다. 이 문제를 풀면서 다시한번 구현이 약하다는 것을 느꼈습니다. 단순 구현문제 같은데 사소한 실수가 많아서 테스트를 성공하지 못한 경우가 많았습니다. 핵심은 문제의 조건을 잘 이해하고 이에 맞도록 구현하는 것이라고 생각합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static int N; static int L; static int[][] map; static void input() t..
문제 개요 최대 8개의 CCTV의 방향을 바꾸어가면서 가장 많은 지역을 감시할 수 있는 방법을 찾는 문제입니다. 문제 접근 최대 8개의 CCTV가 존재하고 4방향으로만 돌릴 수 있으므로 최대 48=65,536 번의 시도가 있어야 합니다. 따라서 최대 시도 횟수가 적으므로 브루트포스로 해결할 수 있습니다. 그래서 백트래킹과 일부 구현을 통해 문제를 해결하였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Camera{ private ..
문제 개요 특정 위치에 벽이라는 요소가 추가되었을 때 최대로 얻을 수 있는 빈 공간의 크기를 구하는 문제입니다. 문제 접근 맵의 최대 크기가 8x8크기이고 3개의 벽을 세울 수 있는 경우의 수는 64C3=41,664 이므로 크기가 작아 부르트포스로 해결할 수 있었습니다. 코드는 빈 공간 중 3개의 위치를 차례대로 선택하고 바이러스가 있는 위치에서 BFS를 통해 감염된 부분들을 구하였습니다. 그리고 빈 공간의 크기에서 바이러스가 있는 크기를 뺀 값 중 가장 큰 값을 출력하도록 하였습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList;..
문제 개요 인구 이동이 한번 발생하는 과정을 사이클이라고 할 때, 총 몇번의 사이클이 발생하는지 구하는 문제입니다. 문제 접근 인구 이동이 발생하는 연합은 BFS나 DFS를 이용해 찾을 수 있습니다. 그리고 Java의 stream을 이용하면 손쉽게 평균을 구할 수 있습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util...
문제 개요 문제가 요구하는대로 구현할 수 있는지를 묻는 문제입니다. 문제 접근 구현을 더 연습해야겠다고 느끼게 해준 문제입니다. 간단한 문제였는데, 로직을 잘못 설정해서 이리 꼬이고 저리 꼬이고 생각보다 많은 시간이 걸렸습니다. 핵심은 N번째 톱니바퀴가 회전할 때 주위의 톱니바퀴의 회전을 재귀함수를 통해 구현한 것이라고 생각합니다. 바뀌기 전 값으로 톱니바퀴가 움직일지 움직이지 않을지 결정해야 하기 때문입니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util...
문제 개요 주어진 위치들을 토대로 M개의 거점 노드에서 다른 일반 노드들간의 최소 거리의 합을 구하는 문제입니다. 문제 접근 문제를 보면서 네트워크 시간에 배웠던 라우팅이 이런식으로 이루어지지 않을까 생각이 들었습니다. 처음에는 MST처럼 그리디로 해결할 수 있지 않을까 생각했었는데, 생각해보니 그리디 조건이 성립하지 않았습니다. 그래서 결국 브루트포스로 해결하였습니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; clas..
문제 개요 다이나믹 프로그래밍을 이용한 스케쥴링 문제입니다. 문제 접근 간단한 문제였는데, 생각을 잘못해서 조금 오래 걸렸습니다. 작업이 진행되는 기간이 주어지기 때문에 이를 고려해서 프로그래밍 해야 합니다. A 상담이 끝나는 시점부터 마지막날까지 최고점이 갱신되어야 했는데, 이 점을 적용하지 않아서 자꾸 틀렸습니다. N값이 작기 때문에 그냥 브루트포스로 풀어도 될 것 같습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; class Pair{ private int duration; private int cost; public Pair..
문제 개요 N개의 숫자와 대응하는 숫자가 주어졌을 때 서로 연결된 숫자들을 구하는 문제입니다. 문제 접근 각 숫자들은 하나의 숫자만을 가지기 때문에 자기 자신을 포함하거나 포함하지 않는 경로가 만들어질 수 있습니다. 따라서 첫 번째 DFS를 통해 경로의 시작 위치를 파악하고 두 번째 DFS를 통해 경로를 구성하는 숫자들을 모두 구할 수 있습니다. HashSet이 정렬된 상태로 저장되는 것이 아니라는 것을 몰라서 틀렸던 문제였습니다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public ..