Dazzling 개발 노트

[백준] 11725 - 트리의 부모 찾기 (Java) 문제 https://www.acmicpc.net/problem/11725 풀이/후기 ArrayList안에 ArrayList를 넣어서 풀이했다. 입력 받을 때 상위, 하위 노드에 대한 구분 없이 그냥 받는거라서 x.add(y), y.add(x)로 양쪽에 넣어두고 bfs를 이용해서 풀면 된다. visited를 이용해 이미 탐색한 노드는 고려하지 않고, parent에 현재 노드를 대입하면 부모 노드를 찾아낼 수 있다. 소스코드로 보는 것이 더 이해가 빠를 것 같다. 난 처음에 x.add(y)이렇게 한 방향으로만 넣어서 풀려다 실패했다(당연한 결과,,^^;) 코드 package GraphTheory; import java.io.*; import java.ut..

[백준] 11052 - 카드 구매하기 (Java) 문제 https://www.acmicpc.net/problem/11052 풀이/후기 카드 N개를 구매하려고 할 때, 1개의 카드팩 구입 후 N-1개 카드 구입 2개의 카드팩 구입 후 N-2개 카드 구입 ... i개의 카드팩 구입 후 N-i개 카드 구입 N개의 카드팩 구입 후 0개 카드 구입 dp배열에는 카드 구매 시 최대 가격이 담겨진다. N개를 구매하고자 할 때 기본적으로 N개의 카드팩이 주어지니까 구입하고자 하는 카드의 개수(N)와 동일한 카드팩(N) 한개만 사는 경우가 존재한다. 즉, dp[N]의 기본값은 P[N]이다. 여기서 다른 개수의 카드팩을 조합하여 N개를 구매하는 경우를 고려한다. 위에서 생각한 것처럼 i개의 카드팩을 구매 후 N-i개를 추..

[백준] 1699 - 제곱수의 합 (Java) 문제 https://www.acmicpc.net/problem/1699 풀이/후기 일단 필요한 제곱수를 미리 계산해서 num배열에 넣어주었다. num = {1,4,9,...} 처음에 생각한 점화식(오답) dp[i] = Math.min(i / num[j] + i % num[j], dp[i]); 점화식을 찾아낸 것에 뿌듯해하고 있었는데, 13에서 예외 상황이 발생했다. 내 점화식대로 하면 4 + 4 + 4 + 1 그러나 13은 9 + 4로 바로 표현될 수 있다. 제곱수끼리의 합으로 표현되는 경우인데 원래 점화식에서 이 부분만 수정을 해줄까 했으나 결국 점화식이 틀려서 발생된 상황이라 새로운 접근법을 생각해야 했다. dp[i] = Math.min(dp[i - nu..

[백준] 1699 - 제곱수의 합 (Java) 문제 https://www.acmicpc.net/problem/1699 풀이/후기 일단 필요한 제곱수를 미리 계산해서 num배열에 넣어주었다. num = {1,4,9,...} 처음에 생각한 점화식(오답) dp[i] = Math.min(i / num[j] + i % num[j], dp[i]); 점화식을 찾아낸 것에 뿌듯해하고 있었는데, 13에서 예외 상황이 발생했다. 내 점화식대로 하면 4 + 4 + 4 + 1 그러나 13은 9 + 4로 바로 표현될 수 있다. 제곱수끼리의 합으로 표현되는 경우인데 원래 점화식에서 이 부분만 수정을 해줄까 했으나 결국 점화식이 틀려서 발생된 상황이라 새로운 접근법을 생각해야 했다. dp[i] = Math.min(dp[i - nu..

[코드트리] 구슬의 이동 (Java) 문제 https://www.codetree.ai/cote/13/problems/marble-movement?utm_source=clipboard&utm_medium=text 풀이/후기 스터디 시간에 풀게된 문제이다. 처음엔 쉽다고 생각했는데, 한 칸에 여러개의 구슬이 존재할 때 우선순위에 따라 제거하는 작업이 까다로웠다. 그리고 이 문제를 통해 가장 먼저 느낀 것은 '자바의 한계' 였다. 평소에도 코테 준비하면서 파이썬이 훨씬 간단하다는 것은 알고 있었지만, 이번에 특히나 더 그렇게 생각이 된 것 같다. (아마도 스터디원이 파이썬을 통해 객체 정렬을 구현한 것이 간단해 보여서 그랬을까..?) 아무튼 우선순위에 따라 가장 큰 항목을 남기기는 구현을 할 수 있겠는데, 우..

[백준] 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..