4:10의 잘못된 subproblems에 대해서 질문이 있는데요. NS(BCD, 4)으로 갔다고 가정했을 때, 그 다음으로 NS(BD, 1)로 가고 나머지 모두 무게가 1보다 크므로 AC를 고르고 BD를 제외한다고 하면 답이되지 않나요? 그러니까 결국 첫번째 subproblem은 A를 무조건 포함하지만 나머지 3개는 A를 포함할 수 도 있고 않을 수 도 있기때문에 제대로 정의된것 아닌가요?
안녕하세요. 처음 2:23 에서부터는 knapsack문제를 subproblem으로 잘못쪼개는 예를 들고있습니다. 때문에 4:10에서 이야기하는 바는, 늘 물건을 선택하는 방법으로 subproblem이 잘못정의 되었다라는 것을 뜻합니다. 제대로된 kanpsack 풀이는 4:20 부터 시작합니다.
강의 감사합니다. 헷갈리는게 있는데 함수에서 n이 나타내는 의미가 잘 와닿지않아요..제가 이해한대로 적어보면 ns(n,w) 에서 n은 아이템 1번부터 n번 까지 고려하여 선택하되, 1~n 모든 아이템이 선택될수도 있고 아닐수도 있는건가요??그러니까 선택 가능한 목록이 1에서 n인거고 그중 실제로 선택되는갯수는 0개부터 n개까지 라고 볼수있는건가요?? 그리고 이어서 표의 행의 의미를 보면 a : 아이템a만 고려하여 선택하는 경우 ab : 아이템 a, b만 고려하여 선택하는 경우 abc : 아이템 a~c만 고려하여 선택하는 경우 abcd : 아이템 a~d만 고려하여 선택하는 경우 라고 이해하면 되는걸까요??
문제가 막혀서 영상을 찾아보던 중 코드 없는 영상을 볼 수 있어 감사했습니다. 그런데 궁금한점이 있습니다. 테이블을 표현할때 N * W 로 만드셨는데 그렇게 만든 이유가 있을까요? A 가 들어 갈 수 도 있고 아닐 수 도 있는 상황이 계속 있으면 2^N * W 가 되지 않나요?
안녕하세요. 그 관점이 바로 knapsack problem의 시작입니다. Table에서 세로축 A, AB, ABC, ABCD가 있습니다. 여기서 가장 먼저나오는 A라인은 A가 있는경우와 없는경우를 모두 커버합니다. 따라서 첫 두줄에서 A가 선택이 된 경우, 선택이 되지 않은경우와 무게별로 각각의 optimal한 값들을 저장하는 것입니다. 이러한 관점으로 A/AB/ABC/ABCD까지 그리고 무게도 0/1/2/3/4/5까지의 optimal 값으로 table을 채워가게 되면서 N*W 가 됩니다. 냅색문제는 전형적인 DP 문제로서, ua-cam.com/play/PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v.html 이곳에서 더 많은 문제와 풀이를 확인할수있습니다. 감사합니다.
@@jhlee6553 안녕하세요. DP의 정의은 problem을 sub problem으로 나누는 것입니다. 그 과정에서 optimization으로 sub problem의 결과를 저장했다가 다시 쓰는것이구요. 떄문에 명제를 따지자면 'DP문제는 메모이제이션을 항상 사용한다' 는 맞지 않지만, 코딩테스트에서 practical 하게는 맞다고 생각하셔도 됩니다.
안녕하세요. 댓글로 남겨주신 트리는 어떻게 읽어야 할지 모르겠습니다. 다만 첫번째 방법같은 경우는 추가 선택이 안되는케이스가 존재하지 않습니다. subTree에서 상위 tree로 넘어갈시 모든 추가 선택이 되고있습니다. 예를들어서 댓글로 주신 문제같은경우 최대무게는 추 1,3이 선택된 가치 70일것입니다. 이를 만들어낼수있는 케이스가 첫번째 방법에는 존재하지 않을것입니다. 또 궁금한점있으시면 질문주세요. 감사합니다.
안녕하세요. 말씀하신 방법은 제가 이해한것이 맞다면, knapsack의 stackcall을 줄이는 대신 한 레벨에서 비교해야할께 많아진 것으로 보입니다. 때문에 time/space complexity이득을 보지는 않을것같습니다. DP에서 knapsack은 전형적인 문제이기 때문에 머리에 외워두고 apply하는것이 좋습니다.
안녕하세요. 언제나 늘 좋은 설명 감사합니다. 영상을 보다가 이해가 안가는 부분이 있어서 질문 드리는데요. 8:24 까지는 이해를 했지만, 2차원 배열을 그리며 설명을 주신 부분에서 [없는 케이스, A,AB,ABC,ABCD] 에서 "AD" 혹은 "AC"를 고려한 케이스는 어떤 부분에 해당되는 걸까요?
AC는 AB다음에서 B가 선택되지 않은 케이스와 연결되서 생각하시면됩니다. 위의 테이블에서는 weight 4와, ABC가 만나 최초로 value 70이 생긴 케이스를 보시면 됩니다. AD도 마찬가지로 optimal 값이 만들어져간다라고 생각하시면 됩니다. 또 궁금한것 있으시면 질문주세요.
좋은 설명 감사드려요~ 도움 많이 됐습니다.
너무 감사합니다! 냅색 문제 이해가 잘 안되었는데 덕분에 이해하고 갑니다ㅎㅎ
좋은 영상 감사합니다!
많이 배워가고있습니다 ㅎㅎ
덕분에 이해했습니다. 감사합니다.
좋은 강의 감사드립니다! 제가 느끼기에 가장 직관적이고 이해가 잘 가는 해설인거 같아요!
감사합니다. 영상 보시다가 궁금한점 있으시면 질문 댓글로 남겨주세요.
좋은 해설입니다.
영상 너무 잘 보았습니다. 혹시 배낭 안에 물건을 마지막에 리턴하는 코드는 어떻게 짜야할까요?
댓글 잘 안남기는데 덕분에 이해가 너무 잘됩니다!! 결국 DP 문제의 핵심은 솔루션에 대한 점화식을 잘 세우고 초깃값을 기반으로 Bottom up 방식으로 해결하는 것이라거 보면 될까요?
감사합니다. dp는 top down, bottom up 두가지 방법으로 모두 풀수 있습니다. 자세한 내용은
ua-cam.com/play/PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v.html
이곳 리스트에서 확인가능합니다.
4:10의 잘못된 subproblems에 대해서 질문이 있는데요. NS(BCD, 4)으로 갔다고 가정했을 때, 그 다음으로 NS(BD, 1)로 가고 나머지 모두 무게가 1보다 크므로 AC를 고르고 BD를 제외한다고 하면 답이되지 않나요?
그러니까 결국 첫번째 subproblem은 A를 무조건 포함하지만 나머지 3개는 A를 포함할 수 도 있고 않을 수 도 있기때문에 제대로 정의된것 아닌가요?
4:10 에서 물건이 없을 경우 라는게 정확히 어떤 의미 인지 궁금합니다 배낭에 넣기전에 선택지 안에 애초에 존재하지 않았다는 말인가요???
안녕하세요. 처음 2:23 에서부터는 knapsack문제를 subproblem으로 잘못쪼개는 예를 들고있습니다. 때문에 4:10에서 이야기하는 바는, 늘 물건을 선택하는 방법으로 subproblem이 잘못정의 되었다라는 것을 뜻합니다.
제대로된 kanpsack 풀이는 4:20 부터 시작합니다.
강의 감사합니다.
헷갈리는게 있는데 함수에서 n이 나타내는 의미가 잘 와닿지않아요..제가 이해한대로 적어보면
ns(n,w) 에서 n은 아이템 1번부터 n번 까지 고려하여 선택하되, 1~n 모든 아이템이 선택될수도 있고 아닐수도 있는건가요??그러니까 선택 가능한 목록이 1에서 n인거고 그중 실제로 선택되는갯수는 0개부터 n개까지 라고 볼수있는건가요??
그리고 이어서 표의 행의 의미를 보면
a : 아이템a만 고려하여 선택하는 경우
ab : 아이템 a, b만 고려하여 선택하는 경우
abc : 아이템 a~c만 고려하여 선택하는 경우
abcd : 아이템 a~d만 고려하여 선택하는 경우
라고 이해하면 되는걸까요??
문제가 막혀서 영상을 찾아보던 중 코드 없는 영상을 볼 수 있어 감사했습니다.
그런데 궁금한점이 있습니다. 테이블을 표현할때 N * W 로 만드셨는데
그렇게 만든 이유가 있을까요?
A 가 들어 갈 수 도 있고 아닐 수 도 있는 상황이 계속 있으면 2^N * W 가 되지 않나요?
안녕하세요. 그 관점이 바로 knapsack problem의 시작입니다. Table에서 세로축 A, AB, ABC, ABCD가 있습니다. 여기서 가장 먼저나오는 A라인은 A가 있는경우와 없는경우를 모두 커버합니다. 따라서 첫 두줄에서 A가 선택이 된 경우, 선택이 되지 않은경우와 무게별로 각각의 optimal한 값들을 저장하는 것입니다. 이러한 관점으로 A/AB/ABC/ABCD까지 그리고 무게도 0/1/2/3/4/5까지의 optimal 값으로 table을 채워가게 되면서 N*W 가 됩니다.
냅색문제는 전형적인 DP 문제로서, ua-cam.com/play/PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v.html 이곳에서 더 많은 문제와 풀이를 확인할수있습니다. 감사합니다.
안녕하세요 강의 잘 보고있습니다 :) 저는 DP란 메모이제이션을 사용하는 알고리즘이라고 알고 있었는데, 해당 문제는 Problem-SubProblem 관계는 있지만 메모이제이션을 사용하진 않는 것 같은데 맞을까요?
안녕하세요. 10:47의 왼쪽 아래 테이블을 보시면 초록색 element들이 공유가 되는것을 볼 수 있습니다. 만약 주어진 knapsack의 조건이 더 촘촘하다면 더 많은 memoizatio을 활용할 수 있습니다. 또 궁금한점 있으시면 댓글로 질문 주세요. 감사합니다.
@@user-pw9fm4gc7e 제가 착각을 했네요 해당 문제에서도 메모이제이션이 이용되는군요! 그럼 'DP문제는 메모이제이션을 항상 사용한다'라는 명제가 참인 것으로 알고 있어도 될까요?
@@jhlee6553 안녕하세요. DP의 정의은 problem을 sub problem으로 나누는 것입니다. 그 과정에서 optimization으로 sub problem의 결과를 저장했다가 다시 쓰는것이구요. 떄문에 명제를 따지자면 'DP문제는 메모이제이션을 항상 사용한다' 는 맞지 않지만, 코딩테스트에서 practical 하게는 맞다고 생각하셔도 됩니다.
선생님 subproblem 나누눈방법 두개 있잔아요.
(1)n-idx선택: for i in range(idx,range(arr))
(2) 2선택: 넣고다음가기, 안넣고다음가기
첫번째것은 잘못나눈거라고 하셨는데요. 두방법 트리 그려보니깐 같다고나오는데...
DP때문에 두번째방법을 택한건가요? 아니면 다른 이유가 있을까요?
__________
| 가치:30 20 40 10 10 Target:5
| 무게:1 2 3 4 5
|
(두개다 무게정렬하고, 프룬닝한 트리입니다)
(여기 숫자12345는 원소ABCDE와 매칭됩니다)
_______________
| (1)n-idx선택 f(T) = max( [f(T-1)+30, f(T-2)+20, f(T-3)+40, f(T-4)+10, f(T-5)+10] )
| 1 2 3 4 5
| 2 3 4 5x 3 4x 4x 5x
| 3x 4x
|
| (1,2) (1,3) (14) (2,3) (3) (4) (5) (무게 pair들)
__________
| (2) 2선택 (넣고다음가기, 안넣고다음가기)
| 1 x | 2^1 f(T) = if -1
안녕하세요. 댓글로 남겨주신 트리는 어떻게 읽어야 할지 모르겠습니다.
다만 첫번째 방법같은 경우는 추가 선택이 안되는케이스가 존재하지 않습니다.
subTree에서 상위 tree로 넘어갈시 모든 추가 선택이 되고있습니다. 예를들어서 댓글로 주신 문제같은경우 최대무게는 추 1,3이 선택된 가치 70일것입니다. 이를 만들어낼수있는 케이스가 첫번째 방법에는 존재하지 않을것입니다. 또 궁금한점있으시면 질문주세요. 감사합니다.
@@user-pw9fm4gc7e 아! 감사합니다 선생님.
제가 첫번쨰방법을 착각을 했습니다. 선생님이 지적하신 첫번째방법은 permutation으로 한부분이였네요.
제가 생각했던방법은 다른 implementation부분이였어요. (combination 찾기때 사용됩니다)
_____________________________________
NS (ABCD,5)
max( NS(BCD,4)+30 , NS(CD,3)+20, NS(C,2)+40 , NS(,1)) (여기서 B선택시, A는없습니다.)
A선택 B선택 C선택 D선택
/ \
NS(CD,2)+20 NS(D,1)+40
B선택 C선택
_____________________________________
def dfs(idx,T):
return max( [ dfs(i+1,T-w[i])+v[i] if 0
안녕하세요. 말씀하신 방법은 제가 이해한것이 맞다면, knapsack의 stackcall을 줄이는 대신 한 레벨에서 비교해야할께 많아진 것으로 보입니다. 때문에 time/space complexity이득을 보지는 않을것같습니다.
DP에서 knapsack은 전형적인 문제이기 때문에 머리에 외워두고 apply하는것이 좋습니다.
@@user-pw9fm4gc7e 감사합니다 선생님!
설명 감사해요. 근데, 코딩을 시작한지 얼마 안되어서 설명이 코딩으로 어떻게 구현되는지 모르겠네요. 혹시 이 문제 코드를 colab에 올려 주실수 있나요? 감사합니다
안녕하세요. 급히만드느라 가독성이 떨어질 수 있습니다.
colab.research.google.com/github/NoCodeProgram/CodingTest/blob/main/dynamicProgramming/knapSack.ipynb
topdown과 bottomUp 방식 둘다 implementation하였습니다.
이해가 안가시는부분 있으면, 질문주세요
감사합니다.
@@user-pw9fm4gc7e 고맙습니다!
안녕하세요. 언제나 늘 좋은 설명 감사합니다.
영상을 보다가 이해가 안가는 부분이 있어서 질문 드리는데요.
8:24 까지는 이해를 했지만, 2차원 배열을 그리며 설명을 주신 부분에서
[없는 케이스, A,AB,ABC,ABCD] 에서 "AD" 혹은 "AC"를 고려한 케이스는 어떤 부분에 해당되는 걸까요?
AC는 AB다음에서 B가 선택되지 않은 케이스와 연결되서 생각하시면됩니다. 위의 테이블에서는 weight 4와, ABC가 만나 최초로 value 70이 생긴 케이스를 보시면 됩니다. AD도 마찬가지로 optimal 값이 만들어져간다라고 생각하시면 됩니다. 또 궁금한것 있으시면 질문주세요.
언젠가 QuadTree에 대해서도 영상 만들어주실수 있을까요???
안녕하세요. 김준영님. QuadTree같은경우는 코딩테스트에서 잘 다루지 않는 DataStructure로 알고있습니다.
먼저 기출문제 레퍼런스를 검색을 해보았는데, Uber에서 2019년에 폰인터뷰로 문제은행식으로 출제된것 이외에는 찾을수가 없었습니다.
혹시 기출문제 레퍼런스 알려주시면 빈도와 중요도 검토후 제작하겠습니다. 감사합니다.
@@user-pw9fm4gc7e 네ㅎㅎ 신경써주셔서 감사합니다!
다좋은데 목소리가 졸려요 ㅎ
안녕하세요. 영상을 정말 졸릴때 만듭니다. 앞으로 졸리지 않은 목소리로 영상 제작하겠습니다. 감사합니다.