PS/LeetCode

문제https://leetcode.com/problems/decode-ways/description/입력1 결과ans: Int = 주어진 s를 알파벳으로 디코딩할 수 있는 경우의 수해석동전 문제와 비슷하게 해석할 수 있다.여기서 제약조건은 알파벳은 1 ~ 26까지 대응되며,  01 , 02 같은 형태는 없는 형태이다. 코드extension String { subscript(_ index: Int) -> String { return String(self[self.index(self.startIndex, offsetBy: index)]) }}class Solution { func numDecodings(_ s: String) -> Int { guard !s.isEmpty..

문제https://leetcode.com/problems/house-robber-ii/description/입력1 결과ans: Int = 훔칠 수 있는 최대 금액해석이전 문제와 동일하지만 제약조건이 하나 추가되었다바로 집 배치가 원형인 점, 이렇게 되면 첫번째 집과 마지막 집도 이웃이되기 때문에 이전 코드는 불가능 첫 번째 집을 방문하면 마지막 집은 무조건 포기한다.첫 번째 집을 방문하지 않고 n-2 번째도 방문하지 않았다면 n번째 집을 방문할 수 있다. 그렇기 때문에 출발 지점과 끝지점이 2개의 경우의 수로 나뉘기 때문에2번의 순회는 필수 불가결 코드class Solution { func rob(_ nums: [Int]) -> Int { let n = nums.count ..

문제https://leetcode.com/problems/house-robber/description/입력1 결과ans: Int = 훔칠 수 있는 최대 금액해석인접 집을 건드리면 안되기 때문에 현재 집을 털기 위해서는 이전 집을 털지 않아야함현재 위치가 i라 할때 필요한 정보는 i-1과 i-2코드class Solution { func rob(_ nums: [Int]) -> Int { let n = nums.count var cache: [Int] = [Int](repeating: 0, count:n) if n == 1 { return nums[0] } cache[0] = nums[0] ..

문제https://leetcode.com/problems/combination-sum-iv/description/입력1 결과ans: Int = nums를 이용해 target을 만들 수 있는 중복조합의 수해석dfs와 memorization을 섞은 문제로 해석 된다.target을 nums에 있는 수 만큼 내리는 top-down 방식으로 해결target이 음수로 가면 가능성이 없으므로 0target이 0이면 1을 리턴 코드class Solution { func combinationSum4(_ nums: [Int], _ target: Int) -> Int { var cache: [Int] = [Int](repeating: -1, count: target+1) cache[0] = 0..

문제https://leetcode.com/problems/word-break/description/입력1 결과ans: Bool = wordDict를 이용해서 s를 만들 수 있는가해석cache[i] = i번째 단어에 도달할 수 있는가를 판단한다.cache[i]가 true면 wordDict에 있는 단어를 하나씩 돌면서 맞는게 있는지 비교코드import Foundationextension String { subscript(_ range: Range) -> String { let startIndex = self.startIndex let from = self.index(startIndex, offsetBy: range.startIndex) let to = self.in..

문제https://leetcode.com/problems/longest-increasing-subsequence/description/입력1 결과ans:Int = 최장 증가 수열길이해석끝지점을 하나씩 늘려가면서, 최장 수열을 기록한다.코드ㅇclass Solution { func lengthOfLIS(_ nums: [Int]) -> Int { let n = nums.count if n == 1 { return 1 } var cache = [Int](repeating:0, count:n) var ans: Int = -1 for i in 0.. nums[j] { cache[i..