Dazzling 개발 노트

[백준] 2225 - 합분해 (Java) 문제 https://www.acmicpc.net/problem/2225 풀이/후기 dp 구조는 dp[x][y]일 때, x개를 이용하여 합이 y인 결과를 얻는 것으로 두고 짜면 된다. 점화식은 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];를 이용하여 풀이한다. 2차원 표로 생각해보면, 구하고자 하는 칸의 바로 왼쪽과 바로 윗쪽 칸의 값을 더하면 원하는 결과를 얻을 수 있다. DP는 점화식만 만들면 쉽게 풀 수 있는데, 점화식을 만드는 것이 너무 어렵다!ㅠㅠㅠㅠㅠ 애초에 dp를 어떤 구조로 생각할지도 감이 잡히지 않아서 결국 검색을 해보았다. 세상엔,, 똑똑한 사람이 참 많고 난 작게 느껴진다,,ㅠㅠ 계속 반복하면서 복습해야겠다..! 코드 p..

[백준] 1325 - 효율적인 해킹 (Java) 문제 https://www.acmicpc.net/problem/1325 풀이/후기 지금까지 dfs/bfs 문제는 항상 2차원배열[][]을 이용해서 풀었는데, 이번 문제는 배열을 이용하니 메모리 초과가 발생했다. 그래서 arrayList를 이용하여 풀었다. 배열, arrayList, LinkedList를 적절한 때에 잘 사용하는 것이 필요한 것 같다. 그 이후에는 일반적인 dfs, bfs 풀듯이 풀이하면 되는데, 이번엔 이차원배열의 형태가 아니라서 for문을 이용해 list 내부를 탐색하는 반복문을 사용하면 된다. 출력은 결과값이 가장 큰 값이 여러개일 수 있어 result 배열에 각 컴퓨터별 해킹 가능 최대개수를 저장해둬야한다. 마지막에 max를 찾아 ma..

[백준] 1654 - 렌선 자르기(Java) 문제 https://www.acmicpc.net/problem/1654 풀이/후기 나무 자르기 문제와 비슷하지만 조금 더 쉽게 풀었다. 렌선의 길이가 커서 double과 BigInteger까지 생각했는데 그냥 long으로 풀면 되는거였다. mid가 0인 경우 나누는 수가 0이되어 오류가 발생하는데, start를 0이 아닌 1로 잡아주니 바로 해결되었다. 코드 package BinarySearch; import java.io.*; import java.util.*; public class Problem1654 { static int K, N; static long[] arr; public static void main(String[] args) throws IO..

[백준] 2805 - 나무 자르기 (Java) 문제 https://www.acmicpc.net/problem/2805 풀이/후기 이코테 책에서 푼 문제와 유사해서 복습 느낌으로 금방 끝날 줄 알았는데, 삽질하는데 시간을 엄청 투자했다,,, - 일단 처음 오답이 나온 부분은 long처리였다. 나무의 합 sum 은 long형태로 사용해야 한다. 이거 외에 별다른 오답 부분이 없는데 왜 자꾸 오답처리가 되는지 한참 고민했다. 결국 찾아낸 부분은 처음 start와 end 설정 부분이었는데, 내가 배열을 정렬한 후 arr[0] 과 arr[N-1]로 지정한 부분이 문제였다. 이렇게 지정하면 배열의 값이 하나인 경우 start와 end가 잘 작동하지 않게 된다. 그리고 내 처음 생각으론 start가 가장 짧은 막대 ..

[백준] 10815 - 숫자 카드(Java) 문제 https://www.acmicpc.net/problem/10815 풀이/후기 수 범위도 정수 범위 내여서 그냥 이진탐색 구현해주면 가볍게 풀 수 있다. 이제 이정도는 가볍게 풀 수 있나보다,,^^; 코드 package BinarySearch; import java.io.*; import java.util.*; public class Problem10815 { static int N, M; static int[] arrN; static int[] arrM; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStream..

[백준] 14501 - 퇴사 (Java) 문제 https://www.acmicpc.net/problem/14501 풀이/후기 5월에 브루트포스 문제 풀다가 만난 문제로 그때 당시 DP 풀이를 보고나서 도망갔던 문제를 다시 풀어보았다. 이제는 DP가 익숙하지만 점화식을 세우는 것은 여전히 어려웠다... 이미 나와있는 점화식을 보고도 이해하는데 한참 걸리니,,^^; 아직도 갈 길이 멀다 싶다 ㅋㅋ 그래도 계속 보다보니 이해가 가긴 한다! 이게 어디야,, dp[t[i] + i] = Math.max(dp[t[i] + i] , dp[i] + p[i]); 그리고 작업을 진행하지 못한 날은 0이 아니라 그 전에 최대값으로 채워줌 dp[i+1] = Math.max(dp[i], dp[i+1]); 코드 import jav..

[백준] 13203 - ABCDE (Java) 문제 https://www.acmicpc.net/problem/13023 풀이/후기 단순 DFS가 아닌 고려해야할 것이 많은 문제 - DFS로 해당 경로 탐색 시 5 이상의 경로가 아니면 방문처리를 다시 false로 수정 필요 : 직접 반례 케이스를 찾아봐야함 - 시간초과 : 구글링으로 고려해야할 부분도 다 고려해줬는데 계속 시간초과가 발생했음 : 모두 배열 형태의 ArrayList를 사용했는데, 난 구조상 이차원배열을 사용해도 될 것 같다고 판단하고 계속 고집함 결국 이차원배열을 ArrayList로 바꾸자마자 정답 처리가 되었다는 후기,,^^; 남들이 안한 이유는 다 있다,, list를 사용해야 시간초과가 나지 않는 이유는 dfs내에서 반복문을 돌 때 N번..

[백준] 2417 - 정수 제곱근 (Java) 문제 https://github.com/allrightDJ0108/CodingTestStudy/commit/26429316cf03dd26ace86644eec2a95eb941a0d7 풀이/후기 BigInteger를 자료형으로 이용해야 한다 long을 이용하여 풀면 틀렸습니다 처리가 된다..ㅎ 0부터 N까지 start, end시점 잡아서 mid보다 큰지 작은지를 따져서 답을 구해주면 된다. 코드 package BinarySearch; import java.io.*; import java.math.*; public class Problem2417 { public static void main(String[] args) throws IOException { Buff..