선생님 질문있습니다

Question

다시 쌤 강의 들으면서 백준, 삼성 sw 문제 풀고 있는데요.
시뮬레이션 문제가 정확히 탐색을 말하는 건가요?

그리고 coinChange 문제에 질문 남겼었는데 그거 추가로 댓글에 질문 또 올렸는데 답변 부탁드립니다 ㅠ dp 너무 어렵네요.

푸샵맨 코딩스터디 · Answer

1. 시물레이션 정확히는 모르겠는데요 백트랙킹, dfs와 유사하다고 보입니다. 느낌아니까 님은 dfs, dp를 힘들어 하시는거 같은데요 dfs는 스택이니까 개념만 아시면되고, 제 문제중에 스택에서 빼서 조건에 걸리게하고 빠지게 하는 방법이 있으니까 집중 풀어보시면됩니다. 2. coinChange DP 문제 질문은 , 저도 5개월전 질문지 찾느라  뒤져서 보고 왔는데요 . 여기에 답글 쓸게요 결국에 우리는 점화식을 구해야 되니까 일일이 만들어 보죠 이게 쉬울겁니다.  모든 문제는 아래와 같은 example을 만들어서 식을 구하는게 나을겁니다. 해답 코드만 먼저 보면 아마 머리가 아프겠죠? 백트랙킹, dfs도 이해가 안되면 여기 백트랙킹 문제도 무식하게 일일이 다 풀어서 결국 식을 만들어 냈습니다. 남이 잘짠 코딩 아무리 봐서 이해가 안되면 뭐합니까, 내가 이해해서 만들면 더 어마무시한걸 만들 수 있는데 온사이트 면접에서는 답이 틀려도 , 이렇게 해를 찾아가는 성의만 보여도 합격했다고 합니다.화이팅~ ================== 동전이 없다 dp[0]=0 이라는 뜻 =============================== 1원 동전이 있을려면, 1원 1개가 필요 dp[1]=1개 이렇게 되야겠죠? 이걸 구할려면 맨오른쪽에 +1일 필요하다는걸 알게됩니다. dp[1] = Math.min(dp[1], dp[1 - coins[j]] + 1); 1-1 = dp[0]=0(앞에서 구한거 이용->재사용이죠?)+1 1-2 = (X)(1 보다 크므로 위에 소스코드 조건절 걸림) 1-5 = (X)(1 보다 크므로  위에 소스코드 조건절 걸림) dp[1] = Math.min(12, 1) 이렇게 나오니까  dp[1] =1을 구한거죠? 이해되시죠? ============================ 2원 동전이 있을려면,2원 1개가 필요 dp[2]=1개 이런 답을 구해야겠죠? dp[2] = Math.min(dp[2], dp[2 - coins[j]] + 1); 2-1 = dp[1]=1+1(앞에서 구한거 이용->재사용이죠?) 2-2 = dp[0]=0+1(앞에서 구한거 이용->재사용이죠?) 2-5 = (X)(-값이 나오므로 패스) dp[2] = Math.min(12, 2) 이렇게 나오니까  dp[2] = Math.min(12, 1) 이렇게 나오니까  결론은, 1원짜리 2개를 쓸거냐, 2원짜리 1개를 쓸거냐 결국 dp[2]=1개 ==================================== 3원 동전이 있을려면,1원 1개가 필요 2원 1개가 필요 dp[3]=2개 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); dp[3] = Math.min(dp[3], dp[3 - coins[j]] + 1); 3-1 = dp[2]+1(앞에서 구한거 이용->재사용이죠?) 3-2 = dp[1]+1(앞에서 구한거 이용->재사용이죠?) 3-5 = (X)(-값이 나오므로 패스) dp[3] = Math.min(12, 2) 이렇게 나오니까  dp[3] = Math.min(12, 2) 이렇게 나오니까  ==================================== 4원 동전이 있을려면, 2원 2개가 필요 dp[4]=2개 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); dp[4] = Math.min(dp[4], dp[4 - coins[j]] + 1); 4-1 = dp[3]+1(앞에서 구한거 이용->재사용이죠?) 4-2 = dp[2]+1(앞에서 구한거 이용->재사용이죠?) 4-5 = (X)(-값이 나오므로 패스) dp[4] = Math.min(12, 3) 이렇게 나오니까  dp[4] = Math.min(12, 2) 이렇게 나오니까  .... ======================================================== 이런식으로 계속 해보면 아..식이 나오는구나 그러면서 실력이 쌓이는거죠~~ 제가 재사용이라고 쓴 부분있죠? 그게 바로 Dynamic Programming입니다. 저걸 이용하면 마치 징검다리처럼 다른걸 찾지 않고 저거만 믿고 태우면 되죠 dp 문제는 난이도가 좀 있어서 ,.. 한번 나온거 맞추면 대박이죠 ..