다른 분들도 저와 같은 고민을 할까해서 댓글 남깁니다! 2579번의 점화식을 다른 방법의1차원 배열로도 풀 수 있습니다 각 계단에 해당하는 배열을 score[i], i번째 계단까지 올랐을 때 받을 수 있는 최대 점수를 total[i]로 하여 배열 2개를 생성한 후, total[1] = score[1] total[1] = score[1] + score[2]로 초기화, 점화식을 total[i] = max(total[i - 2], total[i - 3] + score[i - 1]) + score[i]로 두면 해결 가능합니다! max 함수의 두 번째 인자를 저렇게 둔 이유는 목표로 하는 계단까지 연속하여 3칸 오르는 경우를 배제하기 위함입니다. 두 번째 인자의 경우, 목표 칸보다 전 칸 & 전전전 칸을 밟는 경우입니다. 다른 분들께 많은 도움이 되길 바랍니다!
안녕하세요 바킹독님 덕분에 알고리즘 공부 쉽고 편하게 하고 있습니다.!!! 질문이 하나 있습니다. 1915 - 가장 큰 정사각형 문제 접근입니다. 여러 블로그를 봐도 왜 좌상, 상, 좌 이 세 개의 최솟값을 +1해준 값이 정사각형의 넓이가 되는 건지 이해가 안 됩니다.. 원래 공부를 안 했던 사람이라 이런 이해력이 좀 딸리는데 설명 부탁드려도 될까요?
이게 그림없이 댓글로 설명이 잘 될지 모르겠는데, 일단 d[i][j] 정의는 (i,j)가 우측하단인 정사각형 중 최대 넓이이고 d[i][j] = k라고 하면 d[i-1][j]와 d[i-1][j-1]과 d[i][j-1]이 모두 k-1 이상이어야 해요. 반대로 말하면 d[i-1][j]와 d[i-1][j-1]과 d[i][j-1]중 어느 하나라도 k-1보다 작으면 d[i][j]는 절대 k일수가 없는데 이건 직접 상황을 생각해보시거나 그림으로 표현해서 이해하셔야할듯.. 위의 상황만 이해하고 나면 d[i][j] = min({d[i-1][j], d[i][j-1], d[i-1][j-1]}) + 1; 식은 자명하게 따라와요.
바킹독님 1로 만들기 문제에서, 올려주신 답이랑 똑같은 논리의 코드라고 생각했는데 계속 틀리네요. 놓친 부분이 있을까요? ㅎㅎ 좋은 강의 감사합니다! #include using namespace std; int dp[1000005]; int n; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; dp[1] = 0; for(int i = 2;i
바킹독님 저는 알고리즘 공부하면서 백트랙킹이 제일 어렵더군요....그래서 이리저리 찾아보다가 여기까지 왔는데 우선 백준 랭커신분이 찍은거에 한번 놀라고 강의 퀄리티에 두번 놀랐습니다. 재귀 백트랙킹 듣고 다른 주제도 다 들어보는 중입니다. 좋은 영상 찍어주셔서 감사합니다. 누군가에게 한 줄기 빛입니다 당신은.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 꺄아앙아아아아아아아아앙 젤 궁금했던 내용이었어요!!! 대박 핳 역시 우리 바킹독님이 쵝오에여!ㅠㅠ 행복하당 대상이 혹시 바킹독님인가 했는데 혹시가 역시였군요!!! 진심으로 축하드려욥!!!😆👍🙌🙌🙌다른 공간이었지만 함께 할 수 있어서 영광이었습니댱 컇
강의 너무 잘 듣고 있습니다. 본 영상에서는 다 bottom-up 방식으로만 풀이 하셨는데, 혹 1) top-down 방식과 비교하여 이점이 있을까요? 2) 어떤 문제를 dp로 풀 수 있는 문제라 가정한다면, 해당 문제는 무조건적으로 bottom-up 방식으로 풀수있을까요? 아니면 top-down 방식으로만 풀리는 문제가 따로 있을까요? 개인적으로는 top-down 방식이 더 직관적으로 이해가 잘 되더라구요. 그런데 구글링 했을때 나오는 dp 문제 풀이법들로는 bottom-up 방식이 압도적으로 많아서 두가지 다 익혀야하는지 bottom-up 방식으로만 더 많은 문제를 접해봐야할지 고민입니다.
1. bottom-up과 top-down을 비교해보면 bottom-up은 top-down보다 빠르게 동작하지만 테이블을 채우는 순서를 내가 잘 생각해서 그 순서대로 채우게끔 코드를 짜야한다는 단점이 있습니다 2. (100% 확실하지는 않은데) 모든 DP문제는 bottom-up으로 풀어도 되고 top-down으로 풀어도 됩니다. 저는 테이블을 채우는 순서가 직관적으로 보일 때에는 bottom-up을 쓰고, 순서가 헷갈릴땐 top-down으로 풉니다. 싹 다 top-down으로 풀어도 상관은 없지만 테이블을 채우는 순서를 고민해보는 차원에서 bottom-up으로 풀어보는 것도 괜찮습니다. 참고로 이번 단원에서는 재귀를 어려워할 수 있을 것 같아 bottom-up 방식을 소개하지 않았지만 부록에 "다이나믹 프로그래밍 심화" 단원을 추가할건데 거기서는 bottom-up 방식을 언급할 예정입니다.
안녕하세요 바킹독님 백준 2240 자두나무 질문입니다. 그 전 문제들을 3회독 하면서 dp를 익혔다고 생각했는데, 이번 문제는 초기값 설정을 왜 한 번도 움직이지 않을 때 계속 갱신해서 나아가는지, j값에 따라 i - 1 j- 1 또는 j 값으로 누적하는지 이해가 안 됩니다.. 3차원 베열이 낯설어서 그런걸까요? 자세한 설명을 듣고싶습니다!
@@삼남매의하루-n3x 1149번 느낌으로 자두의 위치가 테이블 인덱스로 들어가고 또 14442번 문제 느낌으로 움직인 횟수를 테이블 인자로 들어가야 한다는걸 알 수 있긴 합니다. dp는 자주 접해봐야 느니 못떠올렸다고 너무 슬퍼하지 마시고 이해하셨다면 다음에 비슷한 문제를 만났을때에는 풀어내겠다고 생각하셔도 됩니다.
바킹독님 안녕하세요! 강의 항상 잘 보고있습니다. 계단오르기 문제에서 초기값에 관련해서 질문드립니다. DP[2][1] 같은 경우 , 연속된 1개의 계단을 밝아서 "2"까지 오는 경우이기 때문에 시작점에서 바로 2계단을 점프하는 경우로 생각이 되는데, 해당 문제에서 "한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다."는 조건 때문에, DP[2][1] 같은 경우에 초기값을 s[2]로 주는게 좀 위화감이 느껴집니다. i,j가 2보다 큰 경우에 위의 점화식이 만족한다고 한다면 상관없지만, 그렇다하더라도 왜 DP[2][1] = S[2]인지 궁금합니다!
d[i] = i번째 계단까지 올라섰을때 밟지 않을 계단의 합의 최솟값, 단 i번째 계단은 반드시 밟지 않을계단으로 선택해야함 이라고 하셨는데... 이해가 잘 가지 않아서 질문합니다 그렇다면 d[1] 은 첫번째 계단까지 올라섰을때 밟지 않을 계단의 합의최솟값이고 첫번째 계단은 반드시 밟지 않을 계단이라고 했으니 아무 계단도 오르지 않은 상태인 0이 되야하는거 아닌가요? 왜 S[1]의 값인 10이 되는지 이해가 안돼요 ㅜㅜ 똑같이 d[2]는 두번째 계단까지 올라섰을때 밟지 않을 계단의 합의 최솟갑이면 2번째 계단을 밟으면 안되니깐 S[1]만 밟고 온경우 10이 되야하는거 아닌가요?
d[i]의 정의는 "밟지 않을 계단"의 합의 최솟값입니다. 그리고 i번째 계단은 반드시 밟지 않을 계단으로 선택한다고 했으니 d[i]에는 s[i]의 값이 들어가야 합니다. 먼저 d[1]을 보면 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 1번 계단을 밟지 않은 계단으로 선택해야 하고, 계단이 1개밖에 없으니 더 따질거 없이 d[1] = s[1] =10입니다. d[2]를 보면 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 2번 계단은 밟지 않을 계단으로 선택해야 하고, 1번 계단은 밟을 계단으로 선택하는게 최솟값을 구할 때 유리합니다. 이 때 d[2] = s[2] = 20입니다. d[3], d[4]를 추가적으로 설명해보면 먼저 d[3]의 경우 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 3번 계단은 밟지 않을 계단으로 선택해야 하고, 1,2번 계단은 밟을 계단으로 선택하는게 최솟값을 구할 때 유리합니다.이 때 d[3] = s[3] = 15입니다. d[4]는 1, 4번 계단을 밟지 않을 계단으로 선택할 때 최소이고 이 때 d[4] = s[1] + s[4] = 35입니다.
13:22 선생님 안녕하세요. 이 부분에 대해서 제가 이해한 게 맞는지 확인받고 싶어서 덧글 남깁니다. [k][1] = 1개의 계단을 올라서 k 번째까지 오는 것이므로 점프하는 경우. [k][2] = 2개의 계단을 올라서 k 번째까지 오는 것이므로 계단을 하나씩 오르는 경우. 이렇게 이해했는데 혹시 제대로 이해한 걸까요? 틀린 부분이 잇다면 알려주시면 감사하겠습니다...
안녕하세요 바킹독님! 늘 좋은 강의 감사드립니다. 22:17에 나온 백준 11726번 정답 코드에서 14번째 줄에 궁금한 점이 있어서 질문드립니다. 위 코드에서는 계산 중간 중간에 계속 10007로 나눈 나머지만을 가져가도록 해야한다고 하셨는데 중간중간에 10007로 나눈 나머지 값들을 더한 것이 d[n] % 10007과 어떻게 같은 값을 가지는 지 궁금합니다. 혹시 모듈러 연산 분배법칙( (A + B) % p = ((A % p) + (B % p)) % p)과 관련이 있는 것인가요? 하지만 대입을 해도 이해가 잘 가지 않습니다.... 알려주시면 감사합니다! 좋은 하루 되세요^^
정수론에서 나오는 성질이긴 하지만 수식으로 복잡하게 생각하기보다는 재귀 단원에서 언급한 것처럼이 우리가 23567385267853+2467889237578198의 끝 자리(=10으로 나눈 나머지)를 계산해야하면 실제 덧셈을 수행하는 대신 자연스럽게 3+8 = 11을 계산해 끝자리가 1인걸 알아내는 것과 동일한 원리로 이해가 가능합니다
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 선생님 knapsack 알고리즘 짜보고 제가 질문 드린 문제와 연관지어 생각해보았는데요, 예를 들어 4를 1 ,2,3을 이용한 합으로 표현할 때 1의 개수는 최대 4개 2의 개수는 2개 3의개수는 1개가 들어갈수 있고 이 7개를 각 item으로 하고 weight 와 value를 (1,1) (2,2), (3,3) 처럼 두고 dp의 값이 4와같은것이 몇개있는지 세면 되는건가요???
선생님 DP 문제집 BOJ 1912 연속합 문제 20번째 줄 코드가 이해가 가지 않습니다. 20번째 줄 코드 : d[i] = max(d[i], d[i-1] + a[i]); d[i-1] + a[i] 보다 a[i]가 크다면 . k+1번째 이후 항 과는 상관없이 누적합이 더 작기때문에 거기까지만 더해야 최대값이다 . 라고 하면 맞는말 인가요 ? 블로그 글 중 구 다이나믹 프로그래밍에서는 이 문제를 다루셔서 코드를 봤는데 현재 코드랑 같은 코드 인건가요 ? 문제 링크를 올리면 댓글이 삭제 되어 문제 번호만 올립니다 ㅜ.ㅜ
같은 코드이긴 한데 d[i] = max(a[i], d[i-1] + a[i]) 혹은 d[i] = max(d[i-1], 0) + a[i]가 더 알아보기 쉬울 것 같네요. 우선 d[i]의 정의는 i번째 항으로 끝나는 연속합 중 최대이고, 선택지는 2가지인데 - 그전의 연속합이 0 이상일 경우 가져오기 (d[i] = d[i-1] + a[i]) - 그전의 연속합이 음수일 경우 버리기(d[i] = a[i]) 입니다.
안녕하세요 강의 잘 듣고있습니다. 계단 오르기 문제에서 테이블 정의가 현재까지 j개의 계단을 연속해서 밟고 라는 문구가 이해가 잘 안됩니다.계단을 연속으로 밟는거 자체가 문제에서 안되는거 같은데 j 개의 계단을 연속으로 밟는 다는게 어떤 의미인지 구체적으로 설명 부탁드립니다 ㅠ (제 생각에는 2개의 계단을 연속으로 밟는거는 연속된 3칸을 밟을 수 없는 규칙에 위배된다고 생각이됩니다.)
12:45 에서 D[k][2] = ? 를 구하는 식에서 D[k-1][1] 만 언급을 하셨는데요... k-2 번째 계단까지 2개의 연속된 계단을 거친경우 D[k-2][2] 값을 갖고 여기서 2칸 점프를 하는 경우 k위치에 도달할 수 있으니(2개의 연속된 계단을 유지하면서) D[k-2][2]인 경우도 고려를해서 max(D[k-1][1], D[k-2][2])로 계산하는게 어떨지 궁금합니다.
for i in range(2,N+1): if i%6==0: D[i]=min(D[i//3],D[i//2],D[i-1])+1 elif i%3==0: D[i]=min(D[i//3],D[i-1])+1 elif i%2==0: D[i]=min(D[i//2],D[i-1])+1 else: D[i]+=D[i-1]+1 에서 i%6은 의미없는 부분일까요?
유튜브가 제멋대로 스팸으로 분류해서 늦게 확인했네요. 6으로 나눠지면 i/2에서 오는거, i/3에서 오는거를 다 고려해야 하는건 맞는데 그래서 15번째 줄에서 else if를 안쓰고 그냥 if를 썼습니다. 6의 배수이면 14, 15번째 줄의 명령이 다 수행됩니다. 닝체님이 달아주신 코드처럼 작성해도 잘 동작하지만 D[i] = D[i-1] + 1 if i % 3 == 0: D[i] = min(D[i], D[i//3]+1) if i % 2 == 0: D[i] = min(D[i], D[i//2]+1) 으로 쓰면 더 깔끔하겠죠.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 1로 만들기 2에서 6으로 나눠지는 경우를 고려하려고 했었습니다. 문제 특성상 min 함수를 못쓰게 됐는데. 이러면 if문을 여러개 써야하고, 만일 고려해질 게 많아진다면 더더욱 늘어나게 될텐데요. 이런상황에서는 그냥 if문을 늘리는 방법밖엔 없나요?
@@BalanceGamers 일단 if문을 과하게 쓰는게 아닌가 싶더라도 본인이 생각하는 로직대로 구현을 성공해보는게 중요하고 이후 다른 사람의 코드를 보며 내 로직에서 개선을 할 부분이 없는가 생각해보면 좋겠죠. 참고로 1로 만들기 2 문제의 경우도 굳이 6으로 나눠지는 경우를 생각하지 않아도 되는 풀이를 본문에서 언급하고 있긴 합니다.
![[바킹독의 실전 알고리즘] 0x11강 - 그리디](http://i.ytimg.com/vi/De0Qg-2O80c/mqdefault.jpg)
![[바킹독의 실전 알고리즘] 0x11강 - 그리디](/img/tr.png)
![[바킹독의 실전 알고리즘] 0x0B강 - 재귀](/img/1.gif)
질문 전에 이 글을 반드시 확인해주세요. 질문 가이드를 정확하게 따라간 질문에 대해서만 답변을 드리고 그렇지 않은 질문은 먼저 가이드에 맞게 수정을 요청할 예정입니다. github.com/encrypted-def/basic-algo-lecture/blob/master/docs/how-to-ask.md
12p(09:23)에서 D[i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단을 반드시 밟아야 함으로 정의해서도 풀이가 가능합니다. 자세한건 문제집에 있는 별해 2 코드를 참고해보세요.
12p(10:07)에서 D[2] = 20 -> D[2] = 30으로 수정합니다.
14p(13:34)에서 D[1][0], D[1][1], D[2][0], D[2][1]을 다 초기값으로 주는게 바람직해요. D[1][0]과 D[1][1]은 주는게 너무나도 당연하고 -> D[1][1], D[1][2], D[2][1], D[2][2]을 다 초기값으로 주는게 바람직해요. D[1][1]과 D[1][2]은 주는게 너무나도 당연하고
22p(21:42) 2xn-2칸 -> 2x(n-2)칸
27p(26:08)에서 D[3] = 2 -> D[3] = 1로 수정합니다.
헤헤 타일링 문제 바로 피보나치 인거 알아내버렸당 이 맛에 공부하는 거지~
다른 분들도 저와 같은 고민을 할까해서 댓글 남깁니다!
2579번의 점화식을 다른 방법의1차원 배열로도 풀 수 있습니다
각 계단에 해당하는 배열을 score[i], i번째 계단까지 올랐을 때 받을 수 있는 최대 점수를 total[i]로 하여 배열 2개를 생성한 후, total[1] = score[1]
total[1] = score[1] + score[2]로 초기화,
점화식을 total[i] = max(total[i - 2], total[i - 3] + score[i - 1]) + score[i]로 두면 해결 가능합니다!
max 함수의 두 번째 인자를 저렇게 둔 이유는 목표로 하는 계단까지 연속하여 3칸 오르는 경우를 배제하기 위함입니다.
두 번째 인자의 경우, 목표 칸보다 전 칸 & 전전전 칸을 밟는 경우입니다.
다른 분들께 많은 도움이 되길 바랍니다!
항상 감사합니다
선생님 안녕하세요 ! 궁금한 점이 있어 댓글 남깁니다. 혹시 dp를 처음 공부하실때 어떻게 공부하셨는지 알 수 있을까요 ? 책도 사서 읽고 문제도 풀어보고 있는데 dp는 해도해도 어려워서 어떻게 공부를 하셨는지 궁금합니다 ! 항상 감사드립니다.
솔직히 너무 오래전이라 잘 기억은 나지 않지만.. 점화식을 잡아내는 수학적 센스를 기르는게 중요한데 이건 그냥 dp 문제들 난이도순으로 쭉 풀어보는 방법밖엔 없어보여요
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 뉴비는 웁니다 ...ㅜ.ㅜ 선생님 덕분에 어려워도 열심히 따라갈수 있게 된거 같습니다. 항상 감사드립니다 !
@@김태우-m3x 빠이탱!
ㅋㅋㅋㅋ이게 프로그래밍이여 씽크빅이여 2xn타일문제보고 씽크빅부터 다시 하기로 마음먹었습니다
안녕하세요 바킹독님 덕분에 알고리즘 공부 쉽고 편하게 하고 있습니다.!!!
질문이 하나 있습니다.
1915 - 가장 큰 정사각형 문제 접근입니다.
여러 블로그를 봐도 왜 좌상, 상, 좌 이 세 개의 최솟값을 +1해준 값이 정사각형의 넓이가 되는 건지 이해가 안 됩니다..
원래 공부를 안 했던 사람이라 이런 이해력이 좀 딸리는데 설명 부탁드려도 될까요?
이게 그림없이 댓글로 설명이 잘 될지 모르겠는데, 일단 d[i][j] 정의는 (i,j)가 우측하단인 정사각형 중 최대 넓이이고
d[i][j] = k라고 하면 d[i-1][j]와 d[i-1][j-1]과 d[i][j-1]이 모두 k-1 이상이어야 해요. 반대로 말하면 d[i-1][j]와 d[i-1][j-1]과 d[i][j-1]중 어느 하나라도 k-1보다 작으면 d[i][j]는 절대 k일수가 없는데 이건 직접 상황을 생각해보시거나 그림으로 표현해서 이해하셔야할듯..
위의 상황만 이해하고 나면 d[i][j] = min({d[i-1][j], d[i][j-1], d[i-1][j-1]}) + 1; 식은 자명하게 따라와요.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 친절하게 답변해주셔서 감사합니다. 다른 문제 더 풀어보면서 감을 익혀볼게요!
바킹독님 1로 만들기 문제에서, 올려주신 답이랑 똑같은 논리의 코드라고 생각했는데 계속 틀리네요.
놓친 부분이 있을까요? ㅎㅎ 좋은 강의 감사합니다!
#include
using namespace std;
int dp[1000005];
int n;
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
dp[1] = 0;
for(int i = 2;i
i가 6의 배수일 때 과연 dp[i/3]+1이 고려되는지 고민해보세요. 그리고 앞으로는 질문 가이드 참고해서 제출 링크를 보내주세요.
바킹독님 혹시 백준 14501 퇴사는 강의가 따로 없나요?? 풀어본 기억이 있는데 바킹독님 강의를 들었던 거 같아서요 ....!
강의로는 없어요
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 아하 헷갈렸너보내요...!
바킹독님 저는 알고리즘 공부하면서 백트랙킹이 제일 어렵더군요....그래서 이리저리 찾아보다가 여기까지 왔는데 우선 백준 랭커신분이 찍은거에 한번 놀라고 강의 퀄리티에 두번 놀랐습니다. 재귀 백트랙킹 듣고 다른 주제도 다 들어보는 중입니다. 좋은 영상 찍어주셔서 감사합니다. 누군가에게 한 줄기 빛입니다 당신은.
안녕하세요, 좋은강의 정말정말 감사합니다!
블로그에도 질문글을 남겼지만, 혹시나해서 유튜브에도 같은 질문을 남겨봅니다.
답변해주시면 너무너무 감사드리겠습니다~~~
04:08
선생님, 안녕하세요. 귀한강의 정말 감사합니다~!
제가 DP정말 초보자라서 그러는데, 혹시 1463번 : 1로만들기 문제에서
d[i] = d[i-1]+1;
if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);
if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);
요부분에서 왜 +1 을 하는지 알려주실 수 있을까요??
12일때 할수있는 연산 3가지가
3으로 나누거나, 2로 나누거나 1을 빼거나 인데,
'1을 빼거나' 에서 +1을 해주는 건 이해가 가는데,
'3으로 나누거나'에서 D[12] = D[4] + 1
'2로 나누거나'에서 D'12] = D[6] + 1
이렇게, +1 을 왜 해줘야 하는지 잘 모르겠습니다 ㅠㅠ
알려주시면 너무너무 감사드리겠습니다~~
블로그에 답글 남겼어요
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 감사합니다~~!!
안녕하세요 바킹독님 좋은 강의 감사합니다
계단오르기 문제에서 밟지않는계단으로 최솟값을 구하는 과정에서 이해가 안되는 부분이 있어서 질문드립니다
바킹독님께서는 d[k-2]와 d[k-3]을 통해서 최솟값을 구하셨는데 d[k-1]은 고려하지 않으신 이유가 무엇인가요?
d[k-1]을 고려한다는건 k-1 계단과 k 계단을 전부 밟지 않겠다는 의미인데 이건 "계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다"는 문제의 상황과 맞지 않습니다
항상 좋은강의 고맙습니당! 바킹독님 그런데 혹시 26:10 에서 D[6] = D[4] + 1 = 2 + 1 = 3 아닌가여? 강의듣고 직접 테이블 채워보는데 궁금해가지구용 ㅎㅎ 점심시간인데 맛점하시길바랍니댱!! 오로라 배경사진 넘 아름다워여! 제 버킷✨오로라보기인데 간접경험한 기분이네여
앗 점심먹고 나니깐 D[6]은 D[5]+1 or D[3]+1 or D[2]+1 중에 더 작은값을 할당하면 된다는걸 깨달았어여! 감사합니다~
@@bluevulpe 좋습니다 버킷리스트 달성 기원합니다🤗🤗
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 고맙습니댱!!🦊💙
@@bluevulpe 아 그리고 저 우리코딩페스티벌 대상 탔슴다,,!!
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 꺄아앙아아아아아아아아앙 젤 궁금했던 내용이었어요!!! 대박 핳 역시 우리 바킹독님이 쵝오에여!ㅠㅠ 행복하당 대상이 혹시 바킹독님인가 했는데 혹시가 역시였군요!!! 진심으로 축하드려욥!!!😆👍🙌🙌🙌다른 공간이었지만 함께 할 수 있어서 영광이었습니댱 컇
강의 너무 잘 듣고 있습니다. 본 영상에서는 다 bottom-up 방식으로만 풀이 하셨는데, 혹 1) top-down 방식과 비교하여 이점이 있을까요? 2) 어떤 문제를 dp로 풀 수 있는 문제라 가정한다면, 해당 문제는 무조건적으로 bottom-up 방식으로 풀수있을까요? 아니면 top-down 방식으로만 풀리는 문제가 따로 있을까요?
개인적으로는 top-down 방식이 더 직관적으로 이해가 잘 되더라구요. 그런데 구글링 했을때 나오는 dp 문제 풀이법들로는 bottom-up 방식이 압도적으로 많아서 두가지 다 익혀야하는지 bottom-up 방식으로만 더 많은 문제를 접해봐야할지 고민입니다.
1. bottom-up과 top-down을 비교해보면 bottom-up은 top-down보다 빠르게 동작하지만 테이블을 채우는 순서를 내가 잘 생각해서 그 순서대로 채우게끔 코드를 짜야한다는 단점이 있습니다
2. (100% 확실하지는 않은데) 모든 DP문제는 bottom-up으로 풀어도 되고 top-down으로 풀어도 됩니다. 저는 테이블을 채우는 순서가 직관적으로 보일 때에는 bottom-up을 쓰고, 순서가 헷갈릴땐 top-down으로 풉니다. 싹 다 top-down으로 풀어도 상관은 없지만 테이블을 채우는 순서를 고민해보는 차원에서 bottom-up으로 풀어보는 것도 괜찮습니다. 참고로 이번 단원에서는 재귀를 어려워할 수 있을 것 같아 bottom-up 방식을 소개하지 않았지만 부록에 "다이나믹 프로그래밍 심화" 단원을 추가할건데 거기서는 bottom-up 방식을 언급할 예정입니다.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 답변 정말 감사합니다. 앞으로의 강의들이 더욱 기대되네요!
안녕하세요 바킹독님 백준 2240 자두나무 질문입니다.
그 전 문제들을 3회독 하면서 dp를 익혔다고 생각했는데, 이번 문제는 초기값 설정을 왜 한 번도 움직이지 않을 때 계속 갱신해서 나아가는지, j값에 따라 i - 1 j- 1 또는 j 값으로 누적하는지 이해가 안 됩니다.. 3차원 베열이 낯설어서 그런걸까요? 자세한 설명을 듣고싶습니다!
일단 테이블의 정의는 이해하셨을까요? 사실 어떤 부분을 헷갈려하는지 파악이 잘 안되어서 좀 더 자세히 질문을 남겨주세요
@@BaaaaaaaaaaaaaaaaaaaaarkingDog3차원 배열이 너무 낯설어서 그런 것 같습니다.
한 번도 움직이지 않을 때를 기준으로 한 번 움직였을 때, 두 번 움직였을 때, w번 움직였을 때를 하나하나씩 최댓값으로 쌓는다고 생각하면 될까요?
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 이런 생각이 팍 떠오르지가 않네요..
@@삼남매의하루-n3x 1149번 느낌으로 자두의 위치가 테이블 인덱스로 들어가고 또 14442번 문제 느낌으로 움직인 횟수를 테이블 인자로 들어가야 한다는걸 알 수 있긴 합니다. dp는 자주 접해봐야 느니 못떠올렸다고 너무 슬퍼하지 마시고 이해하셨다면 다음에 비슷한 문제를 만났을때에는 풀어내겠다고 생각하셔도 됩니다.
바킹독님 안녕하세요! 강의 항상 잘 보고있습니다. 계단오르기 문제에서 초기값에 관련해서 질문드립니다.
DP[2][1] 같은 경우 , 연속된 1개의 계단을 밝아서 "2"까지 오는 경우이기 때문에 시작점에서 바로 2계단을 점프하는 경우로 생각이 되는데, 해당 문제에서 "한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다."는 조건 때문에, DP[2][1] 같은 경우에 초기값을 s[2]로 주는게 좀 위화감이 느껴집니다.
i,j가 2보다 큰 경우에 위의 점화식이 만족한다고 한다면 상관없지만, 그렇다하더라도 왜 DP[2][1] = S[2]인지 궁금합니다!
"해당 문제에서 "한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다."는 조건 때문에, DP[2][1] 같은 경우에 초기값을 s[2]로 주는게 좀 위화감이 느껴집니다. " 라는 말씀이 무슨 뜻인지 잘 이해가 안가요
d[i] = i번째 계단까지 올라섰을때 밟지 않을 계단의 합의 최솟값, 단 i번째 계단은 반드시 밟지 않을계단으로 선택해야함 이라고 하셨는데... 이해가 잘 가지 않아서 질문합니다
그렇다면 d[1] 은 첫번째 계단까지 올라섰을때 밟지 않을 계단의 합의최솟값이고 첫번째 계단은 반드시 밟지 않을 계단이라고 했으니 아무 계단도 오르지 않은 상태인 0이 되야하는거 아닌가요? 왜 S[1]의 값인 10이 되는지 이해가 안돼요 ㅜㅜ
똑같이 d[2]는 두번째 계단까지 올라섰을때 밟지 않을 계단의 합의 최솟갑이면 2번째 계단을 밟으면 안되니깐 S[1]만 밟고 온경우 10이 되야하는거 아닌가요?
d[i]의 정의는 "밟지 않을 계단"의 합의 최솟값입니다. 그리고 i번째 계단은 반드시 밟지 않을 계단으로 선택한다고 했으니 d[i]에는 s[i]의 값이 들어가야 합니다.
먼저 d[1]을 보면 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 1번 계단을 밟지 않은 계단으로 선택해야 하고, 계단이 1개밖에 없으니 더 따질거 없이 d[1] = s[1] =10입니다.
d[2]를 보면 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 2번 계단은 밟지 않을 계단으로 선택해야 하고, 1번 계단은 밟을 계단으로 선택하는게 최솟값을 구할 때 유리합니다. 이 때 d[2] = s[2] = 20입니다.
d[3], d[4]를 추가적으로 설명해보면 먼저 d[3]의 경우 "i번째 계단은 반드시 밟지 않을 계단으로 선택해야함"이라고 했으니 3번 계단은 밟지 않을 계단으로 선택해야 하고, 1,2번 계단은 밟을 계단으로 선택하는게 최솟값을 구할 때 유리합니다.이 때 d[3] = s[3] = 15입니다.
d[4]는 1, 4번 계단을 밟지 않을 계단으로 선택할 때 최소이고 이 때 d[4] = s[1] + s[4] = 35입니다.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 와 ㅜㅜㅜ 이렇게 자세히 설명해주시다니 감사합니다!! 항상 좋은 질의 강의 너무 잘보고 있습니다~~
강의 잘 보고 있습니다! 혹시 14분 8초에서 D[1][2] = 0 인 이유가 뭘까요? 연속해서 2개의 계단을 밟으며 1번째 계단에 올라설 수는 없기 때문에 0이라고 한 걸까요?
넵 맞아요
기다리고 있었습니다...바쁘실텐데 빨리 올려주셔서 감사해요!!
2024-07-13 Kim chan ho lets go..
1. 테이블 정의하기
2. 점화식 잡기
이런 가이드라인 너무 좋네요ㅜㅜ ㅜ감사합니다!
특히 테이블 정의하기에서 dp의 감을 얻을 수 있었습니다..! 정말 감사합니다 ㅜㅜ
13:22 선생님 안녕하세요. 이 부분에 대해서 제가 이해한 게 맞는지 확인받고 싶어서 덧글 남깁니다. [k][1] = 1개의 계단을 올라서 k 번째까지 오는 것이므로 점프하는 경우. [k][2] = 2개의 계단을 올라서 k 번째까지 오는 것이므로 계단을 하나씩 오르는 경우. 이렇게 이해했는데 혹시 제대로 이해한 걸까요? 틀린 부분이 잇다면 알려주시면 감사하겠습니다...
네 맞습니다
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 답변해주셔서 정말 감사합니다!
선생님 혹시 전역변수로 배열 정의하실때 왜 5를 더해주시는지 알수 있을까요 ??
오버플로우를 방지하기 위해서 그냥 습관적으로 배열 크기에 약간 여유를 두는건데 크게 의미를 안두셔도 돼요
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 이해했습니당 답변 감사합니다 !!
바킹독님 점화식을 세우는 과정에서 n번째만 생각하면 된다라는 부분에서 재귀와 비슷하다는 느낌을 받았는데 맞나요?
네 그렇게 볼수도 있는데 이전에 구한 값들로부터 점화식을 만들고 또 이전의 값들을 저장하고 있다는 상황을 이해하시면 좋습니다.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 감사합니다
저번 학기때 dp 문제 푸는것 때문에 엄청 돌려봤었는데 앞부분의 문제들을 거의 다 풀면서 여기까지 왔네요....감사합니다
돌아오셨군요. 이번 영상도 감사합니다!!!
안녕하세요 바킹독님! 늘 좋은 강의 감사드립니다.
22:17에 나온 백준 11726번 정답 코드에서 14번째 줄에 궁금한 점이 있어서 질문드립니다.
위 코드에서는 계산 중간 중간에 계속 10007로 나눈 나머지만을 가져가도록 해야한다고 하셨는데
중간중간에 10007로 나눈 나머지 값들을 더한 것이 d[n] % 10007과 어떻게 같은 값을 가지는 지 궁금합니다.
혹시 모듈러 연산 분배법칙( (A + B) % p = ((A % p) + (B % p)) % p)과 관련이 있는 것인가요?
하지만 대입을 해도 이해가 잘 가지 않습니다....
알려주시면 감사합니다! 좋은 하루 되세요^^
정수론에서 나오는 성질이긴 하지만 수식으로 복잡하게 생각하기보다는 재귀 단원에서 언급한 것처럼이 우리가 23567385267853+2467889237578198의 끝 자리(=10으로 나눈 나머지)를 계산해야하면 실제 덧셈을 수행하는 대신 자연스럽게 3+8 = 11을 계산해 끝자리가 1인걸 알아내는 것과 동일한 원리로 이해가 가능합니다
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 오 덕분에 이해가 되었습니다. 감사합니다!!
선생님 9095 번에 1 2 3으로 표현하기 문제에서요 만약에 1 + 2 + 1 과 1 + 1 + 2 를 같은 식으로 본다고 문제 조건을 바꾼다면 어떻게 문제를 해결할 수 있을까요? 오래 고민해봤는데 잘 모르겟어서요 ㅠㅠ 힌트라도 주시면 다시 한 번 고민해보겠습니다
그것도 dp로 가능해요. 테이블 정의와 점화식 한번 고민해보시고 모르겠으면 knapsack dp라는걸 찾아보세요.
축구 보셨나보네요 ㅋㅋ 이른 시간에 고맙습니다 시도해볼게요
@@hh-hv5xe ㅋㅋㅋㅋㅋ 이젠 자야겠네여 화이팅입니다!
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 선생님 knapsack 알고리즘 짜보고 제가 질문 드린 문제와 연관지어 생각해보았는데요, 예를 들어 4를 1 ,2,3을 이용한 합으로 표현할 때 1의 개수는 최대 4개 2의 개수는 2개 3의개수는 1개가 들어갈수 있고 이 7개를 각 item으로 하고 weight 와 value를 (1,1) (2,2), (3,3) 처럼 두고 dp의 값이 4와같은것이 몇개있는지 세면 되는건가요???
@@hh-hv5xe knapsack 유형중에 물건의 개수가 무한대라고 생각하고 푸는게 있어요. 그러면 무게가 1, 2, 3인 물건이 각각 무한개 있는 상황이랑 이 문제 상황이랑 똑같죠.
바킹독님아 dp를 설명할 때 dag랑 엮어서 생각하는 건 어떻게 생각하시나요? 초보자들한테는 이해하기 무리일까요?
그래프를 아직 안다뤘어서 dag 얘기는 안했는데, 중급 단계를 넘어서려면 필요한 내용이긴 하죠. 근데 저라면 초보자한테는 dag 얘기를 안할듯여
오 답변 감사요
바킹독님 코딩 언제부터 하셨어요?
진짜 머리 좋으신거 같은데... 원래 좋으신건가요 아니면 엄청난 노력을 해서 좋아지신건가요?
코딩 자체는 초5때부터 했고 알고리즘은 고2부터 알았어요. 원래부터 수학을 잘했어서 좀 순탄하게 익혀나간 것 같네요
이거 한달동한 못풀었는데 점화식으로 하니까 바로풀리네요.
너무 감사합니다, DP가 너무 약해서 풀수없었는데 배우고 가네요.
최선을 다하겠습니다!
화이팅입니다!
시뮬레이션에서 머리 깨지고 정렬로 도망쳐서 힐링했다가 다시 DP를 보니 억장이 무너지는것 같네요
바킹독님 강좌 찾아서 정주행하게 된 계기가 그리디, DP에서 개박살이 나가지고 아는게 없어서 그런것 같다 싶어서 찾아보게 된건데 결국 또 만나네요 따흐흑
다시 보면 줘팰수있습니다
21:39 왜 남은 건 2xn-2칸인가요.... ㅜㅠ
2x(n-2) 칸이에요
와 직접 답장 주실 줄 몰랐는데ㅜㅠ 정말정말 감사합니다:) 덕분에 좋은 영상들로 코테 공부하고 있습니다👍🏻👍🏻 @@BaaaaaaaaaaaaaaaaaaaaarkingDog
@@syj4716 지금 보니 2xn-2 칸이 오해의 소지가 있어보여서 고정 댓글에 2x(n-2) 임을 언급해두었습니다 감사합니다 화이팅하세요~~
선생님 DP 문제집 BOJ 1912 연속합 문제 20번째 줄 코드가 이해가 가지 않습니다.
20번째 줄 코드 : d[i] = max(d[i], d[i-1] + a[i]);
d[i-1] + a[i] 보다 a[i]가 크다면 . k+1번째 이후 항 과는 상관없이 누적합이 더 작기때문에 거기까지만 더해야 최대값이다 . 라고 하면 맞는말 인가요 ?
블로그 글 중 구 다이나믹 프로그래밍에서는 이 문제를 다루셔서 코드를 봤는데 현재 코드랑 같은 코드 인건가요 ? 문제 링크를 올리면 댓글이 삭제 되어 문제 번호만 올립니다 ㅜ.ㅜ
같은 코드이긴 한데 d[i] = max(a[i], d[i-1] + a[i]) 혹은 d[i] = max(d[i-1], 0) + a[i]가 더 알아보기 쉬울 것 같네요. 우선 d[i]의 정의는 i번째 항으로 끝나는 연속합 중 최대이고, 선택지는 2가지인데
- 그전의 연속합이 0 이상일 경우 가져오기 (d[i] = d[i-1] + a[i])
- 그전의 연속합이 음수일 경우 버리기(d[i] = a[i])
입니다.
오 신난다 예~
바킹신님 DP 장인이 되게 해주세요
ㅎㅇㅌ,,,,
안녕하세요 강의 잘 듣고있습니다. 계단 오르기 문제에서 테이블 정의가 현재까지 j개의 계단을 연속해서 밟고 라는 문구가 이해가 잘 안됩니다.계단을 연속으로 밟는거 자체가 문제에서 안되는거 같은데 j 개의 계단을 연속으로 밟는 다는게 어떤 의미인지 구체적으로 설명 부탁드립니다 ㅠ
(제 생각에는 2개의 계단을 연속으로 밟는거는 연속된 3칸을 밟을 수 없는 규칙에 위배된다고 생각이됩니다.)
연속된 3칸을 밟을 수 없는거지 연속된 2칸을 밟을 수는 있죠. 예를 들어 내가 1, 3, 4번 계단을 밟았으면 현재까지 2개의 계단을 연속해서 밟은거고 이 경우는 D[4][2]에서 고려가 됩니다.
갓킹독님 1463번 DP말고 BFS로도 풀어봤는데 메모리 초과가 나더라고요, 제가 방문 처리를 안해서 그런가 생각해봤는데 해당 문제는 방문처리를 하면 안되지 않나요? 왜냐하면 해당 칸 까지의 거리중 최솟값을 덮어씌워줘야하니 방문 했다고 방문을 안하면 안되지않나요!?
1에서 뻗어나가는 방식으로 구현하면 될텐데(백준 숨바꼭질 문제처럼) 잘못된 방법으로 구현한 것 같네요. 어떤 방식으로 구현한건지 코드를 보여주세요.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 오잉 답글을 달아도 계속 삭제가 됩니다!
@@헤이호-o7q 유튜브에서 스팸으로 분류하는 것 같은데 블로그 방명록이나 댓글에 남겨주세요
0x10강 - 다이나믹 프로그래밍 문제집 클리어
12852번 값테이블에서 D[3] = 1 아닌가요? 3/3 = 1 해서 한번연산으로 바로 1로 갈 수 있으니까요!
넵 D[3] = 1 맞습니다. 고정한 댓글 보시면 수정한다고 써주었습니다!
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 앗 그렇군요 ㅠ 가려져 있어서 못봤네요! 답변 감사합니다! 항상 명료하고 깔끔한 좋은 강의 제공해주셔서 도움이 정말 많이 되고 있어요!🥰🥰
계단 오르기 문제 예전에 풀었던 포도주 시식 문제랑 완전 똑같은 줄 알고 코드 똑같이 짰다가 크게 혼났네요 ㅜㅜ
계단 오르기 문제는 다음 계단을 무조건 1~2칸 이내로 밟아야 한다는 조건이 있어서 풀이가 달라지는 건가요?
많이 비슷한 문제긴해요. 테이블도 거의 비슷하게 세우지는 것 같은데..
12:45 에서 D[k][2] = ? 를 구하는 식에서 D[k-1][1] 만 언급을 하셨는데요... k-2 번째 계단까지 2개의 연속된 계단을 거친경우 D[k-2][2] 값을 갖고 여기서 2칸 점프를 하는 경우 k위치에 도달할 수 있으니(2개의 연속된 계단을 유지하면서) D[k-2][2]인 경우도 고려를해서 max(D[k-1][1], D[k-2][2])로 계산하는게 어떨지 궁금합니다.
D[k][2]는 "현재까지 2개의 계단을 연속해서 밟고" 라는 조건이 있기 때문에 k-1번째 계단을 반드시 밟아야하고, 그렇기 때문에 D[k-2][2]는 고려가 되지 않습니다.
바쁘신거 다 끝나고 강의 완결나면 2차원 dp도 찍어주세요오
부록에 있는 다이나믹 프로그래밍 심화에서 다룰 예정입니당
항상 감사합니다!! 바킹독님 😄
저번에 DP에서 좌절하고 오랫만에 다시 풀어보니 역시 어려웠지만 계단오르기를 혼자 풀어서 기분 좋아졌네요. 역시 DP는 계속 풀어봐야 하는 것 같습니다.
다음 강좌도 기다릴게요~~ 즐거운 추석되세요~~
정주행 하였습니다! 좋은 강의 감사합니다
바킹독님, 강의 잘 듣고 있습니다. 목표가 있어 첫편부터 강의랑 문제집 보면서 열심히 따라가고는 있는데요. 오늘 DP 1932 에서 좌절을 맛봤습니다 ^^; 반복학습만이 답이겠죠 .. 항상 감사합니다.
두드리면 열립니다ㅎㅎ,,,^^ 화이팅입니다
이런 강의가 왜 지금까지 조회수가 이거밖에 안되는걸까요.. 너무 깔끔한 강의 잘봤습니다.
230921 감사합니다!
감사합니다 정말좋네요~ 지우지말아주세요!!
알고리즘 독학중인데 덕분에 공부하는 방향이 잡히고 있습니다. 항상 감사합니다 !!
1463에서 만약 6으로 나눠진다면 min(d[i],d[i/2]+1,d[i/3]+1) 전부 고려해야 하지 않나요?
for i in range(2,N+1):
if i%6==0:
D[i]=min(D[i//3],D[i//2],D[i-1])+1
elif i%3==0:
D[i]=min(D[i//3],D[i-1])+1
elif i%2==0:
D[i]=min(D[i//2],D[i-1])+1
else:
D[i]+=D[i-1]+1
에서 i%6은 의미없는 부분일까요?
유튜브가 제멋대로 스팸으로 분류해서 늦게 확인했네요. 6으로 나눠지면 i/2에서 오는거, i/3에서 오는거를 다 고려해야 하는건 맞는데 그래서 15번째 줄에서 else if를 안쓰고 그냥 if를 썼습니다. 6의 배수이면 14, 15번째 줄의 명령이 다 수행됩니다. 닝체님이 달아주신 코드처럼 작성해도 잘 동작하지만
D[i] = D[i-1] + 1
if i % 3 == 0: D[i] = min(D[i], D[i//3]+1)
if i % 2 == 0: D[i] = min(D[i], D[i//2]+1)
으로 쓰면 더 깔끔하겠죠.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 와.. 그러네용 감사합니다.
@@BaaaaaaaaaaaaaaaaaaaaarkingDog 1로 만들기 2에서 6으로 나눠지는 경우를 고려하려고 했었습니다. 문제 특성상 min 함수를 못쓰게 됐는데. 이러면 if문을 여러개 써야하고, 만일 고려해질 게 많아진다면 더더욱 늘어나게 될텐데요. 이런상황에서는 그냥 if문을 늘리는 방법밖엔 없나요?
@@BalanceGamers 일단 if문을 과하게 쓰는게 아닌가 싶더라도 본인이 생각하는 로직대로 구현을 성공해보는게 중요하고 이후 다른 사람의 코드를 보며 내 로직에서 개선을 할 부분이 없는가 생각해보면 좋겠죠. 참고로 1로 만들기 2 문제의 경우도 굳이 6으로 나눠지는 경우를 생각하지 않아도 되는 풀이를 본문에서 언급하고 있긴 합니다.
강의 너무 깔끔합니다!! ㅎㅎ
다만 자막이랑 유튜브 진행바랑 같은 선상에 있어서 끊어서 강의를 보면 자막을 못 본다는 아쉬움이 있네요 .
킹독이형 설명 너무잘하고~
감사합니다 도움이 많이되고있어요^^
DP 정말 너무너무어려워요,,, 그래프나 시뮬레이션 이런 건 골2도 잘푸는편인데 dp는 골5만되도 힘드네요 ㅠㅠㅠㅠ
쥬륵.. 문제를 많이 풀어서 이겨냅시다
DP가 가장 어려워요 ㅠㅠ
응애... 하나도 이해가 안가ㅠㅠ
😵