출저 : https://www.acmicpc.net/problem/1107 "브루트 포스의 존재, 순서" 예전에 분명히 풀었던 문제인데 풀질 못했다. 반성해야겠다. 해당 문제는 브루트 포스 즉, "다해보기" 문제이다. 재귀적으로 가능한 경우의 수를 모두 검색한다. 그렇다면, 언제 까지 재귀를 돌릴 것인가? 즉, 기저사례가 언제 일까? 나는 현재 입력으로 들어온 채널의 길이 +1 까지를 기저사례로 정했다. 번호를 눌러서 갈 수 있는 채널들로부터 목적지 채널까지 거리를 비교해줬다. (처음에는 번호를 누르는 것과 동일하게 +,- 버튼도 함께 돌려 버려서 이상한 결과가 나왔다.. 51 > (-) > 50 > 0 > 500 이런 식으로...) 아무튼... 버튼을 누르고, 해당 위치에서 목적지 채널까지 거리를 비교..
출저 : https://www.acmicpc.net/problem/3006 "세그먼트 트리...?" 문제를 풀고나서 시간이 오래 걸려 찾아 보았더니 이 문제는 세그먼트 트리를 이용해서 풀어야 한다고한다. 하지만, 허접인 안는 세그먼트 트리가 뭔지 몰랐고, 생짜 구현했다. 세그 먼트 트리에 대해서 공부한 후에 다시 풀어봐야 겠다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475import java.io.BufferedReader;import java.io.IOException;import java.io...
출저 : https://www.acmicpc.net/problem/6087 "BFS는 갈수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요." 거울 설치(https://www.acmicpc.net/problem/2151) 와 같은 문제이다. 다른 조건을 최소화하는 경우를 구할 때는, 다익스트라 혹은 우선순위 큐를 사용한다. 더해서 BFS는 항상 갈 수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899..
출저 : https://www.acmicpc.net/problem/1347 "시뮬레이션" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays; class Main { static int N; static char[][] map = new char[250][250]; static int maxX; static int maxY; static int ..
출저 : https://www.acmicpc.net/problem/2980 "시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; class Main { static int N,L; static int[] map; static Node[] nodes; static int cur, time; public static void main..
출저 : https://www.acmicpc.net/problem/3985 "시뮬레이션" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; class Main { static int L,N; static int[] map; static int[][] dist; static int max1,max2,idx1,idx2; public static void main (String[] arg..
출저 : https://www.acmicpc.net/problem/3197 "이분탐색, 맵 재정의" 문제는 이분 탐색을 통해서도 풀 수 있고, 우선순위 큐를 통해서도 풀 수 있다. 더 나아가.. union find ? 를 통해서도 풀 수 있다는데 잘 모르 겠다. 이번 풀이에서는 우선순위 큐를 사용해서 풀도록 한다. 사실 더 좋은 풀이가... 있는 것 같긴 하다 ㅠ 메모리 소요와 시간 초과가 너무 크다. 몇일 고생하다가 푼 문제라... 어쨌든 풀리긴 풀려서 다행. 그럼 풀이를 하면 가장 먼저 맵을 재정의 해야 한다. char[][] map 이외에 int[][] 형 맵을 별도로 두어 각 빙판이 몇일 째에 사라지는지를 마킹 한다. 그렇게 한 후, 이분 탐색을 한다면 빙판을 다 녹여보아서 end 값을 구하고, ..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo "DFS와 BFS 를 이용한 단순 구현, 깊은 복사" 벽돌이 쌓여있는 격자에서 W의 열 중에 깰 수 있는 벽돌들의 경우를 DFS를 이용하여 탐색한다. BFS를 이용해 선택한 벽돌의 숫자 만큼 상,하,좌,우 벽돌을 탐색하여 해당 턴에 삭제될 벽돌들을 넣고 벽돌을 삭제 시킨다. 그리고 공중에 떠 있는 벽돌들을 아래로 내려준다. 이 과정에서 나는 깊은 복사를 사용했다. 시뮬레이션 중에 백트래킹이 힘들 경우에는 깊은 복사를 사용하는 것도 좋은 방법 인 것 같다. map 의 크기가 작다면 옅은 복사나 깊은 복사나 그렇게 큰 차이가 없다고 ..
출저 : https://www.acmicpc.net/problem/2151 "다른 조건을 최소화 하는 경우를 찾으려면 우선순위 큐 혹은 다익스트라!" 해당 문제와 비슷한 유형의 문제들이 많다. 목적지 까지 가는 길에 무엇을 한 최소 횟수를 구하는 등의 문제들이 있다. 다익스트라로 풀거나 우선순위 큐로 풀 수 있다. 나는 우선순위 큐를 사용해서 풀었다. 맨 처음에는 우선순위를 그냥 '-1' 과 '0' 으로만 주어서제대로 탐색이 되지 않았다. 비교 대상과의 차이를 우선순위로 두어서 내가 원하는대로 탐색하게 할 수 있었다. 우선순위 큐를 쓸 때는 디버깅이 힘든 것 같다. 우선순위 체크를 할 때 매우 신중히 해야 할것. 더해서 목적지 까지 찾아가는 문제의 경우 어떻게 하면 중복되는 부분을 체크하고 줄일 수 있는..
출저 : https://www.acmicpc.net/problem/3108 "연결 요소의 개수. 빠진 조건이 없나 다시보자. 그리고 아이디어" 해당 문제를 하루 동안 붙잡고 있었다. 어떤 문제든 주어지는 조건을 잘 봐야겠다. 이 문제는 연결 요소의 개수를 구하는 문제로 처음에는 각 좌표에다가 +500 씩해서 모든 직사각형을 map에 체크하려고 했다. 하다보니 하나의 사각형이 내포되면서 접하고 있는 사각형 두개의 경우 탐색이 불가능한 것을 알았고, *2를 해서 벌려 놓을까 하다가 비효율적인 것 같아서 아래 방법으로 풀었다. BFS를 통해서 연결된 직사각형을 구한다. 이 과정에서 각각의 직사각형들이 서로 연결되어 있는지 확인해야 하는데, 나는 연결 되어 있 지 않은 경우를 체크했다. 비교는 x1,y1,x2,..
- Total
- Today
- Yesterday