예전에 풀었던 프로그래머스 거리두기 확인하기와 비슷하다고 느낀 문제였다. 이번 문제는 탐색보다 구현에 더 초점이 맞춰져 있던 것 같다. 요즘 코테를 보면서 느낀 코테 트렌트는 구현인 것 같다. 특정한 알고리즘을 알아야 풀 수 있는 문제도 몇 문제 있었지만 대부분이 구현 문제였다. 그래서 구현 문제를 중심으로 연습해야 할 것 같다. 문제를 읽고 이렇게 나누어 로직을 짰다. 1. 치킨 집중에서 m개를 선택해 조합 구하기 2. 구한 조합으로 각 집마다 치킨 거리 구하여 최솟값을 선택 3. 각 집에 최솟값을 더하여 도시의 치킨 거리 구하기 4. 모든 조합을 돌면서 도시의 치킨 거리의 최솟값을 반환 다만 이 로직이 맞는지 확신이 들지 않았지만 떠오르는 게 이 방법밖에 없어 코드로 구현했다. 구현하며 몇 번 막혔던..
문제 이름은 평범한 배낭이지만 전혀 평범하지 않다고 느꼈다. 한참을 고민하다가 검색을 했지만 너무 어려웠다. 대표적인 DP 문제라고 하는데 knapsack 알고리즘을 이용해서 풀어야 한다. 입력값을 w 배열과 v 배열에 삽입하고 각 무게와 가치를 계산해서 dp배열에 가치의 최댓값을 넣어주면 된다. 가장 이해하기 어려웠던 부분은 아래의 코드인데 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); 이전에 계산했던 가치, 남은 무게의 가치 + 현재 가치 중 큰 값을 저장하는 부분이다. j - w[i] 는 j의 무게에서 현재 아이템의 무게를 뺀 값이다. 이 값은 dp[i-1][j - w[i]] 에 이미 저장되어 있고 이 값에 현재 아이템의 가치를 더한..
문제의 그림부터 DP 문제라고 알려주고 있었다. 꽤나 많은 문제들을 풀면서 이제 문제를 보면 어떤 유형인지 대충 어떻게 설계를 해야 하는지는 알 수 있다. 다만 실제로 구현하는것은 아직도 조금 힘들다. 입력값을 배열로 만들고 마지막 배열의 값을 dp 배열에 복사하는 것이 첫 번째이다. 그리고 정점의 노드부터 재귀를 통해 내려온다. 마지막 노드에 도착하면 왼쪽과 오른쪽의 값 중 큰 값을 선택하고 배열의 값과 더해 dp의 값이 된다. 이런 식으로 모든 노드를 순회하면 dp[0][0] 값이 최댓값이 되어 출력하면 된다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; pu..
문제가 쉬운 듯하면서도 이해가 자꾸 되지 않아서 꽤 시간을 썼다. 부분 수열이 무엇인지 알아야 하고 LIS 알고리즘을 코드로 구현해야 한다. 한 번에 점화식이 떠오르지 않고 한 단계씩 생각해봐야 해서 힘들었다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine(..
