좋은 강의 감사드립니다. 6:16에서 설명해주신 space complexity를 O(1)으로 줄이는 코드가 class Solution { public: int minCostClimbingStairs(vector& cost) { vector v{0, 0}; int size = cost.size(); for(int i = 2; i
안녕하세요. 공부가 싫어요님. DP문제는 여러가지 유형이 있습니다. 가장 쉬운 유형의 문제는 최소비용 계단 오르기 처럼 문제에서 물어보는 global optimum solution이 그대로 subproblem optimum solutions 로 나뉠수있는 케이스입니다. 문제를 보자마자 n-1, n-2인 케이스가 바로 생각이 나는 케이스입니다. 이런케이스는 DP 챕터에서 초급문제로 계속해서 다룰 것입니다. 두번째 경우는 subproblem이 문제에서 물어보는 solution에서 살짝 비트는 경우가 있습니다. kadane's algorithm이 대표적인 경우인데 이런 경우에도 훈련이 된다면 큰 문제없이 해결이 가능할것입니다. 첫번째,두번째같은 케이스의 작은 팁이라고 한다면 "몇가지 방법이 있는가" 같이 방법의 갯수 물어보는 케이스는 대부분 DP로 풀린다고 보시면됩니다. 이 두가지 말고 더 어려운 케이스들이 있습니다. 마치 two pointers나 sliding window, sorting혹은 hashMap을 사용해야 할것처럼 보이지만 답이 안나오는 케이스들이 있죠. 그런경우에는 bottom up 방식으로 한개가 있다면? 두개가 있다면? 세개가 있다면? 이런식으로 유추할수밖에없습니다. 이런 케이스는 어쩔수없이 다양한 방식의 문제에 노출이 되는수밖에없습니다. 결론적으로 "몇가지 방법이 존재하는가?"를 직접적으로 물어보면 DP일 확률이 높고, bottom up방식으로 한번즈음은 생각을 시작해보는것도 DP로 시작할수있는 방법중에 하나입니다.
학교에서 강의듣다가 포기하다가 시험앞두고 만나는 고퀄의 영상이네요 😂
형님 정말 감사합니다. 열심히 공부해보겠습니다!!!
이전까지 DP 문제를 해결할때는
Space complexity를 생각하지 않았는데,
영상을 보고 더 깊은 고민을 하게 되네요…
항상 잘 보고 있습니다 감사합니다!😊
넘 잘 듣고 있어요!!! 감사합니다
와 leetcode 70번 풀다 이게 왜 피보나치랑 똑같은지 궁금했었는데 감사합니다
좋은 강의 감사드립니다.
6:16에서 설명해주신 space complexity를 O(1)으로 줄이는 코드가
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
vector v{0, 0};
int size = cost.size();
for(int i = 2; i
네 맞습니다.
좋은 강의 감사합니다. 질문이 있는데요, 모든 top-down DP문제는 bottom->up 방식으로도 풀수 있을까요?
네 모든 DP문제는 top down, bottom up 풀이 가능합니다.
다이내믹 프로그래밍도 처음에는 재귀적으로 문제를 해결할 수 있느냐를 판단하는게 중요한걸로 알고있는데요.
혹시 문제를 보고 재귀적 사고 방식으로 문제를 해결할 수 있는지 작은 팁같은것들이 있을까요 ?
안녕하세요. 공부가 싫어요님.
DP문제는 여러가지 유형이 있습니다.
가장 쉬운 유형의 문제는 최소비용 계단 오르기 처럼 문제에서 물어보는 global optimum solution이 그대로 subproblem optimum solutions 로 나뉠수있는 케이스입니다. 문제를 보자마자 n-1, n-2인 케이스가 바로 생각이 나는 케이스입니다. 이런케이스는 DP 챕터에서 초급문제로 계속해서 다룰 것입니다.
두번째 경우는 subproblem이 문제에서 물어보는 solution에서 살짝 비트는 경우가 있습니다. kadane's algorithm이 대표적인 경우인데 이런 경우에도 훈련이 된다면 큰 문제없이 해결이 가능할것입니다.
첫번째,두번째같은 케이스의 작은 팁이라고 한다면 "몇가지 방법이 있는가" 같이 방법의 갯수 물어보는 케이스는 대부분 DP로 풀린다고 보시면됩니다.
이 두가지 말고 더 어려운 케이스들이 있습니다. 마치 two pointers나 sliding window, sorting혹은 hashMap을 사용해야 할것처럼 보이지만 답이 안나오는 케이스들이 있죠. 그런경우에는 bottom up 방식으로 한개가 있다면? 두개가 있다면? 세개가 있다면? 이런식으로 유추할수밖에없습니다. 이런 케이스는 어쩔수없이 다양한 방식의 문제에 노출이 되는수밖에없습니다. 결론적으로 "몇가지 방법이 존재하는가?"를 직접적으로 물어보면 DP일 확률이 높고, bottom up방식으로 한번즈음은 생각을 시작해보는것도 DP로 시작할수있는 방법중에 하나입니다.
@@코드없는프로그래밍 "몇 가지 방법이 존재하는가?" 너무 좋은 방법인 것 같습니다.
안녕하세요
강의 잘 보고 있습니다.
혹시 추가로 sliding window나 two pointers관련 영상은 제작하시는지 궁금합니다 ^^;
채널 array챕터에서 다루고 있습니다. 감사합니다.
ua-cam.com/play/PLDV-cCQnUlIYFOXYzqLoXnEye4WxDa_30.html
@@코드없는프로그래밍 감사합니다 ^^