DP 동적계획 다이나믹 프로그래밍 알고리즘 설명 10분만에 이해하기 (정수 삼각형 문제풀이)
Вставка
- Опубліковано 12 чер 2022
- 개발자로 취직하기의 DFS 입문 강의 보러가기
파이썬 : www.inflearn.com/course/pytho...
자바 : www.inflearn.com/course/%EC%9...
다이나믹 프로그래밍, DP, 동적 계획 유형은 코딩 테스트를 준비한다면 꼭 한번은 다뤄야 하는 어려운 주제입니다. 어려운 주제인 만큼 정수 삼각형이라는 예제와 함께 자세하게 설명하다 보니 길어졌는데, 이 영상을 보시면 DP가 왜 필요하고, 문제를 보고 DP를 써야겠다고 판단하는 방법, 그리고 어떻게 풀지까지 완벽하게 이해되실 것을 약속합니다.
많은 분들이 DP에 걸려서 코딩 테스트를 포기하는데 이 영상이 큰 도움이 됐으면 좋겠습니다.
코테 준비 화이팅 하세요!
00:28 다이나믹 프로그래밍의 목적
02:40 정수 삼각형 풀이 (DP)
07:48 DP 문제를 구분하는 기준
10:22 DP 문제 접근 방법
#DP #동적계획 #알고리즘 - Навчання та стиль
늘 영상 잘 보고 있습니다!!!!!
정말정말 감사드립니다 ㅠㅠㅠㅠㅠㅠㅠㅠ
영상 항상 봐주셔서 감사해요 :) 더 좋은 영상 조만간 올릴게요!
도움이 많이 되었습니다 감사합니다 🙏🙏
감사합니다 ㅎㅎ DP가 쉽지 않은 알고리즘이라 많은 연습이 필요하겠지만, 그래도 개념이라도 잘 이해되도록 도울 수 있어서 다행이네요 :)
감사합니다!
네 감사합니다 :) 화이팅하세요!
와.. 이 채널 진짜 보물같습니다!
보물까지..! ㅎㅎ 최고의 칭찬 감사하고 좋은 영상들 더 많이 올릴게요!
너무 설명을 잘해주셔서 마지막 짤처럼 저절로 학습되는 느낌입니다ㅋㅋ 좋은영상 감사합니다!!!!
도움 되셨다니 다행이네요 ㅎㅎ 좋은 영상 많이 올리겠습니다!
설명을 참 잘하시네요 감사합니다😊
감사합니다! DP 관련 문제들은 따로 재생 목록으로 정리하고 있어서 같이 참고하시면 도움 될 것 같아요 :)
ua-cam.com/play/PLlV7zJmoG4XJOSotNY8Fm3FES6c2y4gTy.html
영상이 너무너무 설명도 잘해주시고 팁도 많이 주시고 편집에도 힘쓰신게 보이십니다!! 다른 영상들도 정독해보겠습니다 넘 감사합니다❤😃
진심어린 칭찬 너무 감사합니다 ㅠ.ㅠ 좋은 영상들 많이 올려서 보답할게요!! 정독하시다가 궁금한 점은 편하게 질문해주세요!
덕분에 좋은 내용 잘 보고 갑니다
감사합니다.😄
감사합니다! 더 필요하신 내용 있으면 언제든 댓글 부탁드려요
최고입니다
감사합니다 !:)
와우... 설명과 정성 미쳤네.. 감사합니다
정성까지 인정해주셔서 감사해요 ㅎㅎ 더 좋은 영상 많이 올릴게요!
진짜 이해 잘되네.. 최고에요 모든 알고리즘영상 정독중입니다
감사합니다 우진님 :) 더 좋은 영상 많이 올릴게요! 요즘 바쁘다고 많이 못 올렸는데 곧 복귀하겠습니다! 힘 나는 댓글 감사합니다!!
아 연출 편집 내용 다 완벽하네 바로 구독!
감사합니다 ㅎㅎ 더 좋은 영상 얼른 만들어 올릴게요
와 이제껏 DP 설명 여러영상과 글을 통해 접했는데 이 영상이 가장 쉽고 직관적으로 설명해줘서 이해가 잘되네요 ! 감사합니다!!
최고의 칭찬이네요 ㅎㅎ 너무 좋은 댓글 감사합니다! 좋은 영상들 계속 올릴게요:)
영상 잘봤습니다 도움이 되네요
네 박예린님 감사합니다:) 코딩테스트 준비 화이팅하세요!
댓글 거의 달아본 적 없는데 설명이 너무 감탄스러워서 달아봅니다... 감사합니다!
감탄까지... ㅎㅎ 감사합니다 조한준님 더 좋은 영상들 많이 준비해서 올릴게요! 공부 화이팅 하세요 :)
완벽한 영상이네요
감사합니다! ㅎㅎ
정말 감사합니다
감사합니다! 좋은 영상 많이 만들겠습니다 ㅎㅎ
감사합니다.
감사합니다 성호님 :)
어떻게 이렇게 설명을 잘 하시는지… 감탄이 나오네요. 많이 도움 됐습니다. 감사합니다!
도움이 많이 되셨다니 너무 감사하네요 ㅎㅎ 더 좋은 영상 많이 올리겠습니다! DP 유형이 가장 직관적으로 이해가 안되는데, 반대로 이해하게 되는 순간 느껴지는 희열(?)이 있더라고요. 포기하지 마시고 화이팅 하세요 규현님 :)
감사합니다
감사합니다~
설명 진짜 잘하시네요
도움 되셨다니 다행이고 댓글 남겨주셔서 감사합니다 ㅎㅎ 힘내서 좋은 영상 많이 만들게요!
참 선명하게 다가오는 강의입니다. 많이 연습해볼게요 좋은강의 정말 감사드려요
선명하다는 표현이 참 힘이 되네요 ㅎㅎ 더 직관적이고 이해하기 쉬운 영상 많이 올릴게요!
군더더기가 없어 영상 내내 집중이되고 이해가 잘돼요 정말 감사합이다
감사합니다!!
이제 코테 준비해야할꺼같아서 영상 우연히 발견했는데 좋은 참고가 된거 같습니다. 구독 눌렀습니다!
루잠님 안녕하세요! 구독 감사합니다 :) 코테와 취업 전반에 필요한 영상들 잘 정리해서 공유드릴게요! 코테 준비 화이팅입니다 :)
큰 도움이 되었습니다. 감사합니다!
감사합니다! :)
알고문제 풀다 모르겠으면 지피티쌤한테 물어보는데, 유독 오늘 문제는 죄다 생소한 dp로 풀어보라는 야속한 ai쌤...
그러던중 이 영상 보고 실마리를 찾았습니다!!! 근데 기억하며 풀기라는 너무 좋은 번역을 두고 사람들은 왜 동적 프로그래밍이라는 번역을.... 너무 감사합니다 선생님!!
동적 프로그래밍이라는 이름은 정말 답답합니다 ㅠ 영어가 dynamic programming이라 직역하신 거겠지만... 이런 용어는 한글로는 더 직관적이게 바꿔도 좋을 것 같습니다 ㅎㅎ 도움되셨다니 다행입니다!!
감사합니다! 좋은 영상 잘 봤습니다.
네 도움 되셨다니 다행입니다. 더 좋은 설명 영상들 많이 만들게요 ㅎㅎ
@@gaebal ㅠㅜ 진짜 도움 많이 됐습니다!!! 덕분에 백준 부수고 있어요 ㅎㅎ
이 어려운 개념을 너무 쉽게 설명해주시네요. 감사합니다.
도움 되셨다니 다행입니다 ㅎㅎ 감사합니다!
그 어떤 비싼 강의보다 더 이해가 잘됩니다..
영상 많이 올려주시면 좋겠어요!!
목소리도 좋으셔서 듣기도 편합니다
좋은영상 감사합니다 ㅎㅎ
최고의 칭찬이네요... ㅎㅎ 영상이 길어져서 고민 되기도 하고 너무 편집도 오래 걸렸는데 내박자님이 좋으셨다는 것 만으로도 잘한 것 같아요.
더 좋은 영상 잘 준비해볼게요!
잘 배우고 갑니다
손스타님 좋은 댓글 감사합니다 :) 더 좋은 영상 많이 만들게요!
최근 한달 동안 DP문제들만 집중적으로 찾아서 풀었었는데, DP를 이해하는 부분에만 정말 긴 시간이 걸렸습니다.
다른 분들이 풀이로 올려놓은 코드를 봐도 이해하는데만 정말 몇시간이 넘게 걸리더라고요..
특히 Top-Down의 재귀 방식은, 한달 이라는 시간을 투자했는데도 문제를 봤을 때 어떻게 구현을 해야 되는건지 도무지 감이 안잡히네요..
그래도 문제를 많이 풀어보는게 답이라고 하시니.. 꾸준히 포기 않고 계속 풀어보겠습니다.
마침 DP를 집중적으로 푸는 중이었는데 힘이 되는 영상이네요 ㅠㅠ 오늘도 좋은 영상 감사합니다!
그쵸.. DP가 정말 감 잡기가 쉽지 않은 것 같아요. 저도 여전히 어려운 문제들도 많고, 정형화되지 않다 보니 하나는 쉽게 풀어도 그 다음 문제도 잘 풀 거라는 보장이 있지도 않더라고요. 그래서 그만큼 여러 풀이들을 경험하는게 중요하니 화이팅 하세요!! 항상 댓글 남겨주셔서 감사합니다 :)
제가 그렇게 많은 알고리즘 강의 영상을 보지는 않았지만 이렇게 이해잘되는 영상은 처음입니다
구독하고 다른영상도 챙겨볼께요!
개인적으로 그리디나 다른 알고리즘 영상도 이렇게 제작해주시면 좋을거 같습니다
DFS/BFS, String 등 자주 나오는 유형들은 정리 되어 있는데 그리디도 준비해볼게요! ㅎㅎ 댓글 감사합니다 :)
dp 어려워서 이마 한번 빡치고 유트브에 쳐보니 이런게 나오네요 이해가 잘되네요 감사합니다
안녕하세요 츄이쁘당님 :) 도움 되셨다니 다행이네요.
마침 최근 영상이 알고리즘 책 추천이었고, 구독자 이벤트도 하고 있어서 아래 영상 한번 참고해보시면 좋을 것 같아요! DP 유형도 다루고 있는 책이에요.
ua-cam.com/video/TAX8jdWWSU0/v-deo.html
오 한방에 이해되요 ㅠㅠ
한방에라니... ㅎㅎ 감사합니다. 도움 되셨다니 다행이에요!
명쾌
감사합니다!!
dp 어렵다 어렵다 햇는데 영상보고 한번에 이해가 되네요 감사합니다 ㅎㅎ
도움 되셨다니 너무 다행입니다!! ㅎㅎ 더 좋은 영상 많이 올릴게요 :)
간결한 설명으로 왜 써야하는지, 언제 써야하는지를 한 번에 알 수 있네요
도움 되셨다니 다행이네요 ㅎㅎ 더 좋은 영상 많이 올릴게요!
늦은 나이에 다시 한번 IT일을 시작해보고자 코딩과 알고리즘을 공부하고 있습니다
저같은 사람도 이해하기 쉽도록 설명해주셔서 감사합니다
DFS/BFS로도 풀수는 있지만
경우의 수가 많아지는 경우에는 (대략 500만개 이상)
중복되고 불필요한 연산을 줄일 수 있는 방법을 찾는 것.
즉, 어느 단계까지 최적의 방법으로 풀었다면,
그 정보를 잘 저장해서 뒤로 돌아가지 않고 현재의 정보로 계속 앞으로 나아갈 수 있는 방법을 찾는 것이라고 이해했습니다.
많이 풀어보면서 감을 쌓아야겠네요
마지막 영상에 책의 내용을 손으로 담아 머리에 후려치는(?) 아이의 모습이 저의 모습같네요 ㅎㅎ
나머지 영상들도 정독하겠습니다
감사합니다
네 감사합니다!! 가끔 막막하다고 느껴지긴 하지만, 많이 풀되 매번 원리에 대해서 고민해보려고 하는 게 최선의 방법인 것 같아요. 더 좋은 영상들 많이 준비할게요!!
나만 알고 싶은 유튜버..
좋은 댓글 감사합니다~ ㅎㅎ 다른 분들에게도 많이 알려주세요 영상 자주 올릴게요!
나도 취할거야
컴공인데 교수님보다 더잘설명하네요 바로구독합니다 더좋은 강의 많이 올려주세요
교수님보다도 잘 이해되셨다니 ㅎㅎ 최고의 칭찬이네요! 감사합니다 강의 많이 올릴게요!
덕분에 감으로만 풀던 DP가 원리를 뚫어보는 계기가 되었습니다
혹시 제가 DP를 파다가 너무 궁금증이생기고 뭔가 이해가 될 것 같은데 안돼서 질문드립니다.
결국 DP문제는 크게 세 가지 유형으로 나눌 수 있는 것 같습니다.
1. 특수한 수열문제(피보나치 수/조합의수/구간합)
2. 순열 조합 중복순열 중복조합 을 DP로 탐색하기
예를 들어
백준 [동전1] 문제의 경우
1 2 5중에서 10을 만드는 중복조합의 수
[계단 오르기] 또는 [포도주 시식] 문제의 경우
3(2+1)과 2로 6을 만들 수 있는 중복순열의수
백준 [평범한 배낭]의 경우
조합의 수를 DP로 탐색하여 최대를 찾는 경우의 수
이렇게 저는 느꼈습니다.
문제가 더 어려워질 경우 결국 수학적으로 순열이나 조합이나 중복이냐 아니냐 이렇게 판단하면 더 깔끔하게 접근할 수 있다고 생각했는데요
혹시 시간이 나신다면 DP로 탐색하며 접근하는 순열 중복순열 조합 중복조합 을 크게 4가지로 각각 차이점과 효율적인 구현 방법을 정리해주실 수 있을까요?
설명을 참 잘하시네요👍
감사합니다 :) 다음 주에는 DP나 Brute force 문제 중 좋은 문제들 골라서 풀어보려고 해요. 영상 올라가면 한번씩 참고해 주세요~!
@@gaebal 네, 감사합니다. 👏
풀이를 자바로 올려주시나요?
@@django3861 네 자바와 파이썬으로 번갈아 올리고 있어요. 최대한 특정 언어에 국한된 문법은 지양하고 파이썬 풀이를 봐도 개념 정도는 이해할 수 있도록 올리고 있습니다 :)
@@gaebal 답변 감사합니다
ㅆㅅㅌㅊ
ㅋㅋ 감사합니다!
알고리즘 설명 보면 맨 마지막에 추천하는 문제들 쭉 알려주시는데 혹시 dp 알고리즘은 없나요?
아직은 없는데 DP도 정리되는 대로 공유드릴게요 :)
구글에서는 코딩면접으로 무조건 DP문제 깔고간다네요 ㅎㅎ. 왜 DP문제를 고집하는지 좀 알거같습니다.. IQ테스트..
맞아요 나름 창의성도 필요하고 많은 고민도 필요한 문제들이라 코딩테스트로 만나긴 싫지만, 잘 짤 수 있다면 여러모로 프로그래밍 하는 실력이 느는 유형인 것 같아요
최적의 해를 찾기위해 해당 노드의 값을 변경해 주는 시점이 언제인가요?
상위노드이서 해당 노드로 갔을 때 인가요 아님 해당 노드에서 방문한 상위노드를 본 다음 값을 수정하는 건가요?
원본 노드의 값을 보존하고 상위노드에서 해당 노드에 들어왔을 때 방문한 상위노드의 값을 갖고 큰 값으로 교체해주는 방식인가요?
그럼 dp삼각형을 만들기 위해 dfs를 한번 돌아야 하므로 전치 코드의 시간은 dfs시간만큼 걸리지 않나요?
주로 해당 노드를 방문했을 때 최적의 해를 한번 계산합니다!
그때 그 전에 해당 노드를 계산하는데 필요한 이전 노드를 활용해서 계산하는 방식이라서,
한 노드를 위한 최선의 노드를 계산했다면, 이후에는 그 노드의 값을 변경하는 경우는 없습니다!
그래서 dp 삼각형을 만들면서 한 노드를 채우고 나면, 해당 노드를 계산하기 위해 필요했던 모든 연산을 생략하게 되기 때문에 dfs보다 훨씬 더 효율적이어지게 됩니다!
Dynamic Programming, DP 이해하면 머 사실상 고수로 인정해야... 설명이 진짜 쩝니데이..
감사합니다 ㅎㅎ 더 많은 영상들 준비할게요!
감사합니다
네 감사합니다! :) 더 필요하신 내용 있다면 알려주세요