매일 조금씩

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의 가장 정석적인 문제라고도 할 수 있는 동전 문제다.  처음에. 뭔가 큰수의 동전부터 갯수를 잡아나가야하는 줄 방향을 잘못잡았는데꼭 구성 동전들로 뺐을 때, 0이 되어야 하는 건 아니고, dp로 금액인 amount를 구성하능한 그러니까 amount 보다 합이 작거나 같은 최소 동전의 수를 구하면 된다.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.mi..

1. DFS (깊이 우선 탐색)DFS는 그래프의 한 방향으로 깊이 들어가서 탐색을 마친 후, 돌아와서 다른 경로를 탐색하는 방식이다. Java에서는 주로 재귀 호출이나 스택 자료구조를 사용하여 구현한다.시간복잡도 : O(V+E) (V: 노드 수, E: 간선 수)DFS 예제 코드 (Java)import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.Set;public class GraphTraversal { private Map> graph; public GraphTraversal(Map> graph) { this.graph = graph; ..