본문 바로가기

Coding Test/Dynamic Programming

 (4)
[Programmers] 42897번 - 도둑질 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897문제 요구사항: 턴 집의 최대 금액을 구해라.시간복잡도: 입력크기는 10⁶ 이므로 시간복잡도는 O(nlogn) 이내 여야한다. (10⁶ × 20 = 2 × 10⁷)2. 문제 풀이1. 문제 접근문제는 다음 2개의 조건이 있다.인접한 집은 동시에 털 수 없다.각 집의 금액 nums[i]는 0 이상이다.i번째 집을 털지 말지에 따라 선택지가 갈리게된다는 것을 알수있다. 구하고자 하는 것은 0 ~ i 까지 턴 집의 최대 금액이다. 4번째 집을 턴다면, 그전까지의 턴 집의 최대 누적합을 구해야한다. 따라서 그전까지의 턴 집의 최대 누적합은 작은 문제이고 앞으로의 턴 집의 최대..
[Leetcode] 198번 - 집도둑 1. 문제 파악문제 링크: https://leetcode.com/problems/house-robber/문제 요구사항: 턴 집의 최대 금액을 구해라.시간복잡도: 입력 크기가 100개이므로 2^n은 안된다.(2^10)^10 = 2^1002^10 = 10241,024^10≈(10^3)^10≈10^1010^10 > 10^8 이므로 시간 복잡도 초과2. 문제 풀이1. 문제 접근문제는 다음 2개의 조건이 있다.인접한 집은 동시에 털 수 없다.각 집의 금액 nums[i]는 0 이상이다.i번째 집을 털지 말지에 따라 선택지가 갈리게된다는 것을 알수있다. 구하고자 하는 것은 0 ~ i 까지 턴 집의 최대 금액이다. 4번째 집을 턴다면, 그전까지의 턴 집의 최대 누적합을 구해야한다. 따라서 그전까지의 턴 집의 최대 누적..
[Leetcode] 70번 - 계단 오르기 1. 문제 파악문제 링크: https://leetcode.com/problems/climbing-stairs/문제 요구사항: n번째 계단을 오르는 경우의 수를 찾아라. 계단은 1칸 혹은 2칸씩 오를수있다.시간복잡도: 입력 크기가 45개이므로 2^n은 안된다.(2^10)^4.5 = 2^452^10 = 10241,024^4.5 ≈ (10^3)^4.5 ≈ 10^13.510^13.5 > 10^8 이므로 시간 복잡도 초과2. 문제 풀이1. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까?일단, 문제의 패턴을 파악했다. 문제의 n >= 1 조건과 점화식의 f(n-2) 때문에, 점화식은 n > 2일때부터 성립한다. 그럼 점화식의 초기 조건은 n = 1일때 1이며, n = 2일때 2이다. 따라서 점화식..
[Leetcode] 509번 - 피보나치 수열 1. 문제 파악문제 링크: https://leetcode.com/problems/fibonacci-number/description/문제 요구사항: 피보나치 수열을 구현해라.시간복잡도: 입력 크기가 30개이므로 (2^10)^3=1,024^3≈(10^3)^3≈10^9이다. 따라서 10^8을 초과하므로 통과를 못할수도 있다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출피보나치 수열은 특정 숫자를 구하기 위해서 그 한칸 앞에 있는 값과 두칸 앞에 있는 값을 더해야한다. 따라서 피보나치 수열의 점화식은 f[i] = f[i-1] + f[i-2]이다. 위의 공식에 따르면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...이다. 만일, 단순하게 분할 정복 기법을 사용해서 10번째 피보나치 ..

티스토리툴바