dp

문제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/climbing-stairs/description/입력1 결과ans: Int = n계단까지 올라갈 수 있는 경우의 수해석한번에 1칸 또는 2칸까지 올라갈 수 있으니 목적지(n) 기준 n-1과 n-2 경우의 수를 더하면 끝 코드class Solution { func climbStairs(_ n: Int) -> Int { if n

문제https://www.acmicpc.net/problem/15486 입력n: Int = 남은 근무 일 t: [Int] = 근무 시간p: [Int] = 일급1 결과ans: Int = 퇴사할 때 최대 수익해석점화식은 문제에서 금방 구할 수 있다.dp[i] = i 날까지 왔을 때 최대 수익 j = i + t[i] = 다시 일을 할 수 있는 날 , i = 1이고, t[i] = 1이면 , 다음일은 2일부터 바로 시작할 수 있다. 하지만 여기서 중요한 점은 일을 많이한다고 수익이 최대가 아니다.  그러므로 현재 i날을 기준으로 전날 까지의 최댓값을 계속 가져가야한다. 코드import Foundationvar t: [Int] = [0]var p: [Int] = [0]let n = Int(readLine()!)!f..

문제https://www.acmicpc.net/problem/11722입력n: Int = 수열의 길이arr: [Int] = 수열 1 결과ans: Int = 가장 긴 감소하는 부분 수열 길이해석LIS의 형태로 간단한 점화식을 세울 수 있다. dp[i] = i 전까지 가장 긴 감소하는 부분 수열 길이 반복문 한개는 i = 현재 값 , 나머지 반복문 j = i 직전까지총 최대 1000 x 1000을 돌며  arr[j] > arr[i] 일 때 dp 배열을 갱신한다. 코드import Foundationlet n = Int(readLine()!)!let arr = [-1] + readLine()!.components(separatedBy: " ").map{Int($0)!} var dp: [Int] = [Int](r..

문제https://www.acmicpc.net/problem/1520 입력n, m = 지도의 행 , 열 길이 arr: [[Int]] = 각 지점의 높이결과ans: Int = 이동 가능한 총 경로 수해석내리막길인지 판별한후 dfs를 통해 목적지에 도달 후 return을 통해 카운팅을 해주자.  코드import Foundationlet nm = readLine()!.components(separatedBy: " ").map{Int($0)!}let (n,m) = (nm[0], nm[1])var arr: [[Int]] = []for _ in 0.. Int { if x == n-1 && y == m-1 { cache[x][y] = 1 return 1 } if..