본문 바로가기

Dynamic Programming

 (5)
[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] 53번 - Maximum Subarray 1. 문제 파악문제 링크: https://leetcode.com/problems/maximum-subarray/description/문제 정의: 배열 요소의 총합이 제일큰 subarray의 총합을 구해라.시간복잡도: 입력크기가 10^5 이기 때문에 시간복잡도는 O(nlogn)이햐여야한다.2. 문제 풀이1. 문제 접근 과정처음에 subarray에서 최대값을 구하는 문제라 슬라이딩 윈도우로 접근했다.하지만 슬라이딩 윈도우로 풀리지 않았다.문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다'라는 것을 발견했다.그다음 그리디 문제처럼 최적의 해를 찾아서 푸는 알고리즘을 도출하였다.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번째 피보나치 ..

티스토리툴바