# dynamic programming
[알고리즘] DP: Dynamic Programming
dp(dynamic programming), 동적 프로그래밍은 크고 복잡한 문제를 작은 문제로 나누어 푸는 알고리즘이다. 비슷한 문제를 반복해서 풀어야 하는 경우에 시간 복잡도와 공간 복잡도를 줄일 수 있다. 크게 Top-Down과 Bottom-Up 방식이 있다.
프로그래머스 - 정수 삼각형
오늘 풀어본 문제는 프로그래머스의 정수 삼각형이라는 문제이다.문제 설명은 다음과 같다.문제 설명\[7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5]위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우
RL(3) - Dynamic Programming
Markov Decision Process를 Dynamic Programming을 이용하여 해결하는 과정에 대해서 알아본다.
다이내믹 프로그래밍 (Dynamic Programming)
하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다.피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다.피보나치 수열의 점화식: D\[i] = D\[i-1] + D\[i-2]이 D\[15]을 구하기 위한 과정을 보
[Leetcode] 198. House Robber
https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-likeddpk를 "k번째 house까지의 최대 rob 합" 으로 정의하고, 식을 세워 값을 채
[CS/Algorithm Study] Algorithm - Dynamic programming
동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이는 분할 정복(Divide and conquer)과 비슷하지만, 한 가지 큰 차이는 '작은 문제의 중복이 발생하지 않도록 한다'는 것이다.
[4코3파] #306. Leetcode 1-D Dynamic Programming (1)
3코1파 2023.01.04~ (306일차)4코1파 2023.01.13~ (298일차)4코3파 2023.10.01 ~ (36일차)2023.11.05 306일차https://leetcode.com/problems/climbing-stairs/문제 설명계단을 오를
[Leetcode] 118. Pascal's Triangle
https://leetcode.com/problems/pascals-triangle/description/?envType=study-plan-v2&envId=top-100-liked이전 레벨의 수들을 통해 다음 레벨의 수를 구하면 되었다.(DP)
[Leetcode] 45. Jump Game II
https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-likedDP를 이용해서 처음에 제출한 풀이는 다음과 같다. 시간복잡도는 O(N^2)으로 AC를
[Leetcode] 70. climbing stairs
https://leetcode.com/problems/climbing-stairs/description/?envType=study-plan-v2&envId=top-100-likedtop down 풀이와 bottom up풀이가 모두 가능하고, 메모이제이션을 통해
D&C와 DP - divide and conquer(분할정복 방식), dynamic programming(동적 프로그래밍)
분할(divide)해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.정복(Conquer - Solve)나눈 작은 문제를 각각 해결한다.통합(Combine - Obtain the solution)필요하다면 해결된 해답을 모은다.Top-down approach(하향식
[BOJ] #12865 평범한 배낭
중요하거나 어려웠던 문제에 대해 작성합니다. > * 2차원 DP > * Knapsack 문제 백준 문제 링크 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기