매일 조금씩

class Solution { public boolean canJump(int[] nums) { int goal = nums.length - 1; // dp는 무조건 배열의 앞에서부터 찾아나간다고 생각했는데 // 여기선 최대 점프수가 주어지니까 골 지점 바로 앞에서시작해서 --하며 시작점까지 도달가능한지 역추적한다.. // goal에 도달가능한 지점이면 goal해당 지점으로 업데이트한다. // 업데이트 되는 goal에 계속 도달가능해서 goal이 계속 앞으로 이동하면. // 거쳐온 모든 뒤의 인덱스들을 통해 무조건 마지막 지점에 도착할수 있으므로 젤 앞의(현재의) goal만 봐도 무방함. for(int i = ..

이것도 dp의 대표적 문제중 하나다. 집을 털때 인접한 옆집을 터는 것과 관련이 있으므로 dp문제 특징 중 하나임.class Solution { public int rob(int[] nums) { int n = nums.length; if(n == 1){ return nums[0]; } // i번 집을 털때 or 안털때에 대한 최댓값을 저장 int[] dp = new int[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); // i번 집을 털때와 안털때 중 큰 값을 dp에 넣기 // 점화식이 성립하는 이..

class Solution { public int combinationSum4(int[] nums, int target) { // 인덱스 숫자가 되기 위한 구성 갯수를 저장하는 배열 int[] sumCount = new int[target+1]; // 선언만으로 모두 0으로 채워짐. sumCount[0] = 1; for(int sum = 1; sum

dp의 정석적인 문제이다. class Solution { public boolean wordBreak(String s, List wordDict) { // 문자열을 첨부터 끝까지 돌면서 사전의 단어와 일치하는지 비교한다. // 일치할때, 그 전의 문자열도 일치했었는지가 중요하다. // 그래서 이를 저장해서 확인할 수 있는 문자열과 비슷한 길이의 배열이 필요하다. // => dp의 중요 개념 중 하나! 저장! boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; // substring 할때 해당 인덱스 전까지 자르므로 1부터 시작! f..

dp의 가장 정석적인 문제라고도 할 수 있는 동전 문제다.  처음에. 뭔가 큰수의 동전부터 갯수를 잡아나가야하는 줄 방향을 잘못잡았는데생각해보니 나누어떨어지도록 해야해서. 작은 수부터 차차 구해서 피보나치 처럼 중복 연산 없게 해야했다. class Solution { public int coinChange(int[] coins, int amount) { int[] ans = new int[amount+1]; Arrays.fill(ans, amount+1); ans[0] = 0; for(int i = 1; i = 0){ ans[i] = Math.min(ans[i], 1 + ans[i-coins[j]]); ..

이문제는 가장 긴 증가하는 부분수열(LIS)을 푸는 방식과 매우 비슷하다. 다만 여기선 가장 긴 감소하는 부분 수열을 찾는 문제이며 최댓값을 찾아내는 것이고 순서는 상관없기 때문에 입력받은 값을 reverse시켜서 가장 긴 증가하는 부분 수열처럼 처리하면 된다. #include #include #include #include using namespace std; int n; vector v; int main(void) { cin >> n; for (int i = 0; i > x; v.push_back(x); } // 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 reverse(v.begin(), v.end()); // 다이나믹 프로그래밍을 위한 1차원 DP..