알고리즘/알고리즘 풀이 (6) 썸네일형 리스트형 Leetcode in Java - 322. Coin Change Greedy가 부적절한 이유Greedy란 현재 상황에서 가장 좋은 것을 택하는 방식이다. 다음과 같은 예제에서 Greedy 전략에 따르면 가장 큰 수부터 take 하기 때문에 11 + 1 + 1로 정답을 3으로 도출하게 됨. 하지만 실제 정답은 6 + 7으로 2개의 동전만 필요함. coins = [1, 6, 7, 9, 11] , amount = 13 DP를 사용해야 하는 경우재귀적인 계산이 필요할 때 : 즉 위 예제에서 13원을 최적으로 거슬러 주기 위해서 10원을 거슬러 주는 방법을 구해야 될 수도 있고, 10원을 거슬러주기 위한 최적의 방법을 구하기 위해서는 5원을 최적으로 거슬러주는 방법을 구해야 될 수도 있는 식이다. subproblem을 한 번 계산 해놓은 것을 거듭 다시 쓸 수 있고 다시 써.. Leetcode in Java - 560. Subarray Sum Equals K Brute Force 풀이법Brute Force 방식으로 nums의 각 원소를 시작점으로 해서, 중첩된 loop를 돌면서 j까지 더했을 때 k가 되는 subarray가 없는지 확인해볼 수 있다. 이때 중첩된 반복문 때문에 시간복잡도는 O(n)이고, 별도의 공간을 사용하고 있지 않기 때문에 공간복잡도는 O(1)이다. // T.C O(n^2)// S.C O(1) 별도의 공간을 사용하지 않음class SolutionBruteForce { public int subarraySum(int[] nums, int k) { int n = nums.length; int count = 0; for (int i=0; i 최적화 힌트1. prefix s.. Leetcode in Java - 238. Product of Array Except prefix[], suffix[] 만들어서 푸는 방법O(n)으로 풀어야 하는 조건이 있어 prefix[]와 suffix[]를 미리 만들어두어야 한다.class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int pre[] = new int[n]; int suff[] = new int[n]; pre[0] = 1; suff[n - 1] = 1; for(int i = 1; i = 0; i--) { suff[i] = suff[i + 1] * nums[i + 1]; } .. Leetcode in Java - 46. Permutations (backtracking) backtracking이란?backtrack은 `후퇴`로 번역되는데, 미로에서 길을 찾을 때와 같이 막다른 길에 도달하면 마지막 선택으로 돌아가는 것을 말한다. backtracking과 다른 알고리즘의 구별모든 가능성을 전부 탐색해야 하는 brute force 방식으로, 각 탐색이 다른 탐색에 영향을 미치지 않으므로 DP와 다르고, 각 후보(candidate)는 다른 후보와 더 낫거나 모자라지 않으므로, 전역 최댓값을 구하기 위해 국소적 최솟값을 선택하는 greedy와도 구별된다. backtracking 전체적인 흐름 backtracking은 모든 가능한 경우의 수를 탐색하여 최종 답안인 집합 S를 구하게 된다. 후보인 s가 S에 포함될지 안될지를 판단후 포함되면 S에 추가하고, 포함되지 않으면 .. Leetcode in Java - 46. Permutations (재귀) 알고리즘 설명 재귀함수는 depth라는 정수를 매개변수로 받는데, 이 depth는 재귀적으로 함수를 호출할 때마다 1씩 늘어난다. depth에 따라 swap 해주어야 하는 배열의 인덱스가 달라지기 때문이다. swap 해주어야 하는 두 인덱스는 depth와 i인데, i는 depth부터 시작해 배열의 끝(n-1)까지 증가한다. depth가 n과 같아지면 swap하지 않고 최종 반환할 리스트에 추가한다. 코드class Solution { public List> permute(int[] nums) { List> ans = new ArrayList>(); perm(ans, nums, 0); return ans; } public void swap(int[] nu.. 위장 수정 후import java.util.*;class Solution { public int solution(String[][] clothes) { int answer = 1; HashMap map = new HashMap(); for (int i=0; i values = map.values(); for (Integer val : values) { answer*= (val + 1); } return answer-1; }} 수정 전 - map.size() == 0 일 때 map.get("key") == null (오류 안남)import java.u.. 이전 1 다음
