해결 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws...
2665번(미로 만들기)
해결 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] dr = {0,-1,0,1}; static int[...
16948번(데스 나이트)
해결 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] dr = {0,-2,-2,0,2,2}; static...
3020번(개똥벌레)
해결 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.net.Inet4Address; import java.util.*; public class Main { static int N,H;...
1967번(트리의 지름)
첫 시도 N은 10^4 가중치가 있는 트리이므로 bfs보다 dfs가 맞는 것 같아 dfs로 구현 모든 노드를 순회하면서 각 노드에서 가장 긴 길이를 찾아 max값과 비교 시간복잡도는 모든 노드 순회 * dfs(최악의 경우 모든 노드 탐색) -> O(N^2) 시간 제한이 2초라 아슬아슬하게 통과 O(N^2)보다 효율적인 코...
7662번(이중 우선순위큐)
첫 시도 Q는 10^6 우선순위큐를 2개 만들어 최솟값, 최댓값을 poll() 한쪽 큐에서 poll 된 값을 다른쪽 큐에서 remove() 답은 잘 나오는데 시간초과 -> O(Q)인데 왜 시간초과? 우선순위큐는 힙으로 구현되어 있음, remove()를 하려면 앞에서부터 순차 탐색 -> remove()의 시간복잡도는 O(...
2295번(세 수의 합)
첫 시도 N은 10^3이므로 x,y,z 3가지 경우의 수를 모두 확인하려면 10^9이므로 완탐 불가 해결방법을 찾지 못해 구글링 해결 x+y+z = k일때 k를 만들 수 있는 경우의 수는 N^3 x+y+z = k를 x+y = k-z로 바꾼다면 N^2으로 구현할 수 있음 추가로 x+y의 값이 저장되어 있는 배열에서 k-z값을...
2149번(암호 해독2)
첫 시도 문제를 잘못읽어 평문을 암호문으로 만드는 문제로 이해 HashMap을 사용해서 키의 문자 1개, 문자열 1줄을 묶어 정렬 그 후 배열에 그대로 넣고 암호화된 문자열을 출력 평문을 만들어야 하므로 실패 해결 HashMap을 사용하지 않아도 해결 가능 키를 배열에 담고 정렬 입력받은 순서...
14584번(암호 해독)
첫 시도 암호문의 길이는 100 이하, N은 20, N의 길이는 20이다. 문제를 해결하기 위해 해야하는 작업이 2가지가 있다 암호문의 모든 문자를 한칸 씩 옆으로 옮기기 -> 모든 경우를 확인해야 하기 때문에 26번 반복 사전에 등록된 단어가 해독된 문자열에 있는지 확인, 1개라도 있으면 해당 문자열이 ...
2851번(슈퍼 마리오)
첫 시도 버섯의 갯수가 10개로 고정, 완전탐색으로도 해결 가능 누적합을 사용 -> (100 - 누적합 값)의 절댓값을 구해 100과 얼마나 가까운지 계산 시간복잡도는 10 -> O(1) 해결 import java.io.BufferedReader; import java.io.IOException; import java.i...