23강 - 다이나믹 프로그래밍 타일링 문제 풀어보기 ② [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #23 ]

23강 - 다이나믹 프로그래밍 타일링 문제 풀어보기 ② [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #23 ] 강의 동영상입니다. 이번 시간에도 지난 시간에 이어서 다이나믹 프로그래밍 타일링 문제를 풀어보는 시간을 가집니다.

[@user-wc8fe7li7j]

멋져요 진짜

[@순수만두]

정말 도움이 많이 됬어요 감사합니다

[@user-ul9yy4hd3m]

아하 동빈님, 마지막 문제에서 첫번째 풀이 때는 d[x] 에 저장할 때 간단한 점화식과 추가개수분을 따로따로 계산하여 마지막에 더하는 것이었는데, 두번째 풀이 때는 d[x][0] 에 저장할 때 횡을 하나씩 더 늘려 추가개수분의 계산을 할 때, 미리 구해놓은 수치를 단순 덧셈을 함에 따라 속도가 빨라 시간초과가 뜨지 않는다는 것이군요! 점점 갈수록 어려워지는데, 동빈님 설명과 함께라면 끝도 없이 잘 헤쳐나갈 수 있을거 같아요! 감사합니다.

[@띠용-l3j3r]

저도 제 생각 적어보면 동빈나님께서 두번째 문제 두번째 방법에서 d[0][0] = 0, d[1][2]= 1로 두셨는데, 반대로 d[0][0] = 1, d[2][1] = 0으로해도 문제가 풀립니다. 그래서 생각해보건데 원래 후자가 맞지 않나 라는 생각이 드네요. 그게 뭔가 올바른 느낌.. 왜냐면 그냥 갑자기 d[2][1] = 1이 떡하니 나오는게 솔직히 좀 설명이 안 되는 부분이잖아요? 그 부분이 왜 1이 나왔냐를 설명하려면 결국 d[0][0]=1이니까 라는 말이 필요하고, 왜 d[0][0]가 1이냐면 아무것도 없는 공간을 표현할 수 있는 방법의 수가 아무것도 놓지 않는다란 1가지 방법이 있으니까, 라고 생각이 드네요. 그냥 제 생각 짓껄여봤습니당 ..

[@띠용-l3j3r]

2주만에 다시봐도 이게 맞는것 같네요. d[0][0] = 1, d[2][1] = 0이게 올바른 것 같습니다.

[@0hyun]

제 생각도 같아요

[@donghunpark379]

d[1][2] = 1 --> d[2][1] = 1 이요.

[@rabe486]

@@띠용-l3j3r 저는 이해가 안가서 그러는데, 조금 더 자세한 설명 부탁드려도 될까요??..

[@뿌요소다-k7p]

카두룩치 저도 이렇게 생각해요. 이게 구현상 더 명확하기도 하구요!

[@kamlious]

상식적으로 길이가 0일 수는 없지만 N이 4일 때 특수한 경우 2개가 있다는 걸 N이 0일 때로 계산하는 것. D[4-4]는 D[0]이니까 상식으로 접근해서 N이 0일 때 0으로 계산하면 특수한 경우를 계속 축적할 수 없음

[@hc-sc9mx]

도대체 왜 d[2][1]이 1이 됩니까??? 진짜 한국 블로그들 다 뒤져봐도 그거에 대한 설명은 쏙 빠져있네요... 너무 쉬워서 당연해서 그런건지...다른 분들도 동일 질문이 많을걸 보니 추가 내용에 한번 써주셔도 좋았을 것 같네요...두시간을 넘게 봤는데도 모르겠네요

[@xerX2]

감사합니다. 1차원 dp 코드에서는 dp[0]=1인데, 2차원 dp코드에서는 dp[0][0]=0 으로 바뀌었네요. 또한 dp[2][1]이 왜 1로 시작하는지 이해가 되지 않습니다. (물론 이렇게 시작해야 풀리긴 하지만요) 전체 개념 많이 배우고 있습니다.

[@김신혜-q1k]

x가 0인경우 왜 1이 나오는건가요?

[@who7875]

안녕하세요 안경잡이 동빈나님 처음 문제에서 if(x==0)return 1;로 해주셨는데 3일때 3을 얻어내기 위한 생각인가요? 그리고 2*N을 세가지 로 채우는 문제에서 n-2로하고 2*2부분을 채울때 1*1 4개를 가지고 구하는 방법은 안되는건가요?

[@박민상-p9d]

그냥 점화식에서 2*dp(x-1) + 3*dp(x-2) + 2 해주면 안되나요? x == 0,1,2 인 경우는 모두 return 값을 정해줬으니 3이상부터 들어간다고 하면 괜찮을 것 같은데

[@don_t_ask_anything]

두 번째 문제의 경우.. 처음부터 메모이제이션으로 풀지 않는 이유가 있는건가요? 2차원배열을 넣는게 더 헷갈리지 않을까요?

[@꿈과희망-y1w]

동빈님 dp 2차원 배열 사용하실 때 두번째 행의 값과 첫번째 행의 값을 더해주는 걸 왜 그렇게 되는지 설명을 안해주셔서 이해가 안갑니다. 왜 그런 건가요? 설명이 점점 생략되는 부분이 많은 것 같아 초심자 입장에서 너무 어렵습니다 ㅠㅠ

[@주식은역시공매도]

동빈님 안녕하세요 ~ 궁금한게 있어서요. 7분25초 (백준14852번) 풀이하실 때 n-2를 채울때 3가지라고 하셨는데 총 6가지의 경우의 수가 나오는 것 아닌가요? 1x1로 모두 채우는 경우, 1x2와 1x1을 사용해서 채우는 경우를 포함시키지 않는 이유가 있으신가요?

[@dongbinna]

보시면, N - 1을 채우는 경우와 N - 2를 채우는 경우로 분류했습니다. 말씀하신 것 중에서 3가지 경우(1x1로 모두 채우거나, 1x2와 1x1을 이용해서 채우는 경우)는 N - 1을 채우는 경우에 이미 포함이 되어있어서, N - 2를 채우는 경우에서는 제외해주어야 합니다.

[@주식은역시공매도]

헐 친절하고 빠르고 명쾌한 답변 감사합니다 ^^ 항상 잘 보고 있어요 =)

[@정재학-x2s]

d[2][1]이 1이 되어야 하는 이유는 단순하게 생각하면 d[3][1]부터 차례로 for문으로 계산해야 하는데 계산에 오류가 안 나려면 d[2][1]에 1을 넣어줘야 하기 때문인 것 같습니다. 어차피 x=2 까지는 굳이 for문으로 안 돌려도 되니까요. 제가 볼 때 d[2][1]가 1인 이유는 그런 것 같네요 계산에 오류 안 나려고 미리 넣어둔 거지 큰 의미는 없는 것 같습니다.... (어디까지나 제 생각입니다)

[@thk6362]

언제나 많은 정보 주셔서 감사합니다. dp입문자라서 질문이 있는데요. 타일채우기 3 문제에서 초기값으로 d[0] = 1 이고 마찬가지로 d[2][1] = 1로 설정하는 부분이 이해가 안갑니다. 시간초과가 나는 코드에서 for 반복문 이 dp[0]까지 돌아서 의문점이 생겼습니다. 즉 d[0]과 d[2][1]의 정의가 궁금하고 도출 방법이 궁금합니다. 단순히 점화식을 맞추기 위해 넣은건가요?

[@동호-v1l]

저도 이 질문 작성자님과 동일하게 궁금하네요. 2차원 배열로 표현할 때 d[0][0] = 1이 되어야 하는게 아닌가요?

[@띠용-l3j3r]

d[0] = 1이 맞습니다. 왜냐하면, 결국 그것도 동적 프로그래밍으로 봤을 때 부분문제이기 때문이지요. 2*1, 1*2로 아무것도 없는 빈공간을 표현할 수 있을까요? 네 있죠. 바로 1개. 아무것도 놓지 않는다. 자료구조 시간에 배우는 트리도 마찬가지입니다. null 즉, 아무것도 없는 것도 트리입니다. 이는 연결리스트도 마찬가지죠. null조차도 연결리스트로 봅니다.

[@tyh3052]

@@띠용-l3j3r 아.. dp[0]은 아무것도 놓지 않는 경우가 되어서 1가지로 카운트 되어야 하는군요..

[@허새-u8w]

마지막,, 4번째 문제 2차원 dp 이해가 안되요..ㅠㅠ 고수님들 설명 좀 부탁드려요 ~~!

[@jihosong9392]

근데 그럼 첫번째문제도 똑같이 시간초과나야되는거 같은데 왜 그냥 패스죠? 두번째 문제랑 다른게 있나요?

[@ASD121-v4c]

동빈님 잘 들었습니다. 궁금한 점이 있어서 댓글 남깁니다. d[0][0] = 0, d[2][1] = 1이 되는 이유가 궁금합니다

[@띠용-l3j3r]

제가 대신 답변 드릴게요. d[0][0]은 동빈님이 사용하신 두번째 해결방법(2차원 배열사용한 DP)을 위해서 0을 두는것입니다. D[2][1]에 1을 넣는 것을 볼 수 있고, 그 뒤로는 D[x][1]번째 값은 항상 D[x-1][1]+D[x-3][0]을 더해서 구하기 때문입니다.