Medium174 [leetcode][39] Combination Sum 문제 : leetcode.com/problems/combination-sum/ 정수형 배열 candidates이 주어질 때 이들을 더해서 target을 만들 수 있는 배열을 구해라. 이 때, candidates 값은 중복해서 더해질 수 있다. 오랜만에 찾아온 백트래킹 친구. fun backtracking(index, target, 저장배열[]) { if (target == 0) 정답배열에 저장배열 추가. if (target < 0) 정답 불가능하므로 종료. for(num = candidates[index, 끝]) { 저장배열 뒤에 num 추가. backtracking(index, target - num, 저장배열) 저장배열 뒤에 추가한 num 삭제. } } 시간복잡도는 O(|candidates| * ta.. 2020. 10. 5. [leetcode][216] Combination Sum III 문제 : leetcode.com/problems/combination-sum-iii/ 1에서 9까지의 숫자 만 사용할 수 있고 각 조합은 고유 한 숫자 집합이어야한다는 점을 고려하여 숫자 n이되는 k 숫자의 가능한 모든 조합을 찾습니다. 숫자 n을 k개의 수의 합으로 만들 때 가능한 조합들을 구하라. 이 때, 수들의 합은 1~9 중 고유한 수들의 조합이다. ex) 가능 : [1,3]. 불가능 : [2,2] -> 2가 겹침 백트래킹으로 풀었다. index 위치에 오름차순으로 숫자(let, i)를 하나씩 대입하면서 n-i, k-1 로 갱신하면서 배열을 만들어나간다. k 혹은 n이 음수가 되면 정답이 불가능한 경우다. n과 k가 모두 0이 되면 정답이 가능한 경우이므로 이때동안 만든 숫자 배열을 정답배열에 추.. 2020. 9. 12. [leetcode][435] Non-overlapping Intervals 문제 : https://leetcode.com/problems/non-overlapping-intervals/ interval 배열이 주어질 때 겹치지 않는 interval 요소들을 남기기위해 최소로 삭제해야 하는 interval 수를 구해라. 최소로 삭제해야 한다. = 가장 많은 interval들이 선택(삭제x)되어야한다. 정렬해서 푸는 그리디 문제이다. 끝 지점을 기준으로 오름차순 정렬시킨다. 끝 지점이 같다면 시작지점이 큰 순으로.(많은 interval 들이 선택되어야 하므로 interval이 작은것들먼저 선택되게 한다.) 선택된 interval들의 끝 지점을 last 변수에 저장한다. 정렬된 interval 배열을 앞에서부터 탐색하면서 탐색중인 interval의 시작지점이 last 변수보다 작다면.. 2020. 8. 16. [leetcode][442] Find All Duplicates in an Array 문제 : https://leetcode.com/problems/find-all-duplicates-in-an-array/ 배열크기가 n 일때, 1이상 n이하의 값을 가지는 int형 배열이 주어진다. 배열 요소들은 한 번 혹은 두 번 존재한다. 주어진 배열에서 두 개가 있는 요소들을 구해라. 주목해야 할 점은 배열의 요소들이 1 이상 n 이하라는 점이다. 이를 이용하여 nums배열 값들을 해당 인덱스 위치(nums[i] - 1)에 이동시킬 수 있다. ex) [1,3,4,2] -> [1,2,3,4] 주어진 배열을 앞에서부터 탐색하면서 nums[i] 위치에 i+1 수가 올때까지 다른 요소값과 교환한다. 그러기 위해서는 nums[i]에 있는 수를 nums[i] 인덱스 위치에 있는 수와 swap한다. 예를 들어 .. 2020. 8. 8. [leetcode][621] Task Scheduler 문제 : https://leetcode.com/problems/task-scheduler/ tasks들이 주어질 때 같은 task(같은 알파벳)은 쿨다운 n이 지나기 전까지 실행이 불가능하다고 하자. CPU가 tasks들을 모두 완료하기 위해 걸리는 최소 시간을 구해라. 문제의 핵심은 가장 많이 나온 task가 가장 많은 idle 을 만들 수 있다는 것이다. 따라서 가장 많이 나온 task로 idle 수를 구한 다음 남은 task 들을 idle에 최대한 채워넣는걸 목표로 한다. tasks = { A, A, A, B, B }, n = 2 일 때를 생각해보자. 쿨다운 n은 동일한 task가 가장 많은 수와 관련이 있다. A _ _ A _ _ A 위의 경우 A가 3개, B가 2개 이므로 A만 채웠을 때 idl.. 2020. 8. 1. [leetcode][309] Best Time to Buy and Sell Stock with Cooldown 문제 : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 주식가격이 주어질 때 최대 이익을 구하라. 동시에 여러개의 교환은 진행될 수 없다. (즉, 주식을 샀으면 팔때까지 다른 주식을 사고팔수없다.) 주식을 팔았을 때 다음날엔 어떠한 거래도 할 수 없다. (쿨다운 1일) 오랜만에 dfs + dp(memoization). top-down 방식으로 풀었다. dfs(index)를 stock[index~]을 사고 팔 때 얻을 수 있는 최대이익을 가져오는 함수라하자. 이 값은 index에서 어떠한 거래도 하지 않았을 때(dfs(index+1))와 index를 샀을때로 나뉠 수 있다. index 번째 주식을 구입했으면 팔아야 .. 2020. 8. 1. 이전 1 ··· 14 15 16 17 18 19 20 ··· 29 다음
