Dazzling 개발 노트

[백준] 16956 - 늑대와 양 (Java) 문제 https://www.acmicpc.net/problem/16956 풀이/후기 스페셜 저지 문제로, 예제에 나온 출력과 내 결과가 달라도 문제의 조건이 맞다면 정답처리가 된다. 처음 예제 출력을 보고 울타리를 어떻게 효율적으로 배치하는 코드를 짜야하는지 막막했다. 그러나 울타리 개수가 한정된 것이 아니고, 효율적으로 배치하라는 조건도 없기 때문에 그저 양과 늑대가 만나지만 않는다면 울타리는 자유롭게 설치가 가능하다. 예제 3 출력을 보면 울타리가 하나 들어가 있는데, 어차피 늑대가 존재하지 않기 때문에 울타리가 없어도 정답이다. 그래서 BFS를 이용해 늑대 주변에 모두 울타리를 설치하는 방식으로 풀었다. 단, 늑대와 양이 1칸 이내에 존재한다면 무조건 ..

[백준] 14889 - 스타트와 링크 (Java) 문제 https://www.acmicpc.net/problem/14889 풀이/후기 백트래킹 유형은 그동안 외면하다가 처음 풀어본 것 같다. 처음에는 그래프탐색이나 DP를 활용한 풀이를 생각했었다. 결국 DFS를 활용한 백트래킹으로 풀었다. N명을 2개의 팀으로 나누기 위해 depth 변수를 활용한다. depth+1을 계속해서 호출하며 N명의 절반이 될 때까지 재귀를 호출한다. 즉, 이렇게해서 팀을 나눈 것이다. 팀은 두개의 팀이기 때문에 true, false로 구분이 가능하다. 나는 true팀, false팀이라고 이해하니 편했다. 그리고 팀이 결성된 후에 각 팀의 점수를 비교하여 최소값을 구해주면 된다. 처음 생각할 때는 어려운데, 소스코드를 보면 또 ..

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

Git에서 변경된 내용을 수정 후 커밋을 눌렀을 때 아래와 같은 상황이 발생했다. main [rejected - non-fast-forward] 라고 뜨는데, 정상적으로 커밋이 된 경우에는 뜨지 않는 문구이다. 이런 경우 내가 커밋한 내용을 제대로 반영하기 위한 방법을 정리해 보았다! 1. Eclipse 내의 Git Repositories 탭을 확인한다. (없다면 Window > Show View > Other > Git Repositories) 2. 내가 커밋하고자 하는 저장소 > Remotes > origin > github 주소 우클릭, configure Fetch 클릭 3. Advanced 클릭 (Ref mappings에 아무것도 없으면 Add를 눌러서 추가) 4. 기존에 있는 항목은 Remove..