coinChange 문제 질문

안녕하세요.

늦게 답을 드려 죄송합니다. 이문제는 상당한 시간을 투자해야합니다.

그래서 답변이 길어질거 같아서 이제 썻네요 ㅜㅜ

1. 이 문제는 dp(dynamic programing) 문제의 핵심이죠

dp는 이미 갈길이 정해져 있고, 재사용 개념이라고 보시면됩니다.(영상참조)

11원 만들기위해서 (1코인,2코인,5코인) 5+5+1을 이용하고 최소값을 찾는거니까 답은 3이죠

2. 우리는 dp[i] 배열을 만듭니다. 무조건 만들어야하죠

예를들어

dp[2]는 2원을 만들기위해서  2원하나를 사용하면 되므로 1

dp[4]는 4원을 만들기위해서 dp[4]=2 입니다.

dp[5]는 얼마죠? 1입니다. 5코인 한개만 이용한다는 뜻이되죠

여기까지는 무조건 이해하셔야합니다.

그럼 질문 주신

"선생님께서 dp array를 0 12 12 12 12 12 .. 로 만드셨는데, 정확히 왜 max를 11이 아닌 12로 두셨는지 잘 모르겠습니다"

12가 아니라 Integer 최대값 21억으로 셋팅해도됩니다. 저값은 dummy라고 보시면 됩니다.

우리는 최소값을 어차피 구하기 때문에 더미로 셋팅한값입니다. max를 11로 하셔도 됩니다.

보통 int max = Integer.MAX_VALUE; 이렇게 많이 씁니다. 이렇게 바꾸고 테스트 해보세요

본론으로

이 문제의 핵심은 

dp[i]= min( dp[i], dp[i-coin[j]]+1)

dp[2]를 구할때, 우리는 직관적으로 2원하나면 되니까 1이라고 압니다.

이걸 구하기 위해서는 아래 과정을 거칩니다.

1. dp[2]= min(dp[2], dp[2-1코인]+1)=min(dp[2], dp[1]+1)=dp[2]에는 12, dp[1]+1은 2죠 

2. dp[2]= min(dp[2], dp[2-2코인]+1)=min(dp[2], dp[0]+1)=dp[2]에는 12, dp[0]+1은 1이죠 , dp[2]=1을 넣습니다.

3. dp[2]= min(dp[2], dp[2-5코인]+1)=min(dp[2], dp[-4]+1)= dp[-4]이니까 if문에서 걸려서 못들어 옵니다.

중요 포인트는 우리는 이미 구한 dp[0],dp[1]을 이용한다는겁니다.

바로 재사용이죠, 우리는 기존의 값을 구한 애들을 이용해서 앞으로를 구해주는겁니다.

이게 dp 문제의 핵심이죠

여기서 dp[2]를 구할때 1번은 기존의 구한 dp[1]에다가 1을 더해줍니다. 1원 2개를 쓰면된다는거죠

근데 2번에서, dp[0]이 나옵니다. 2원을 한버써서 구한거죠

그러니까, dp[0]=0에 의미는 2원을 구하기 위해서 2코인을 한번쓰면 제로가 된다는 의미입니다.

dp[4]를 구할때, 이것도 한번 따져보세요

min(dp[4], dp[4-1코인]+1)=min(dp[4],dp[3]+1)

min(dp[4], dp[4-2코인]+1)=min(dp[4],dp[2]+1)

min(dp[4], dp[4-5코인]+1)=min(dp[4],dp[-1]+1)

이문제는 dp문제중 bottom Up , Top Down 중에 bottom up 방식입니다.

이 문제 하나를 이해하기 위해서 , 1-2시간 투자 안됩니다.

코딩이 그래서 어렵지만, 그 희열이 있습니다.

즐코딩하세요

MAX_VALUE로 두고 할 경우

coins[2] , amount = 3인경우 

음수가 출력되어 정답이 이상하게 나오네요!

결국에 우리는 점화식을 구해야 되니까

일일이 만들어 보죠 이게 쉬울겁니다. 

모든 문제는 아래와 같은 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)(-값이 나오므로 패스)

====================================

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]=2(앞에서 구한거 이용->재사용이죠?)

4-2 = dp[2]=1(앞에서 구한거 이용->재사용이죠?)

4-5 = (X)(-값이 나오므로 패스)

========================================================

제가 재사용이라고 쓴 부분있죠? 그게 바로 Dynamic Programming입니다.

저걸 이용하면 마치 징검다리처럼 다른걸 찾지 않고 저거만 믿고 태우면 되죠

dp 문제는 난이도가 좀 있어서 , 그렇게 쉽사리 출제되지는 않을거여여(참고)

안녕하세요~

먼저 죄송합니다.

댓글의 댓글이라 제가 늦게 확인하게되었습니다.

질문주신내용:

MAX_VALUE로 두고 할 경우

coins[2] , amount = 3인경우 

음수가 출력되어 정답이 이상하게 나오네요!

=> 

MAX_VALUE로 두고 한다는 의미가 Integer 맥스값을 말씀하시는건가요?

제가 정확히 이해가 안되는데요. 혹시 소스로 올려주실수 있나요??

감사합니다.

선생님 추가 설명 감사드립니다 !
어떤 로직인지 이해되었습니다 감사합니다 !

네 선생님 답변주신거 이제 읽었습니다.
제가 알고리즘 공부를 잠시 중단했다가 얼마전부터 다시 시작해서 강의 복습을 진행하고 있습니다 !
여전히 dp는 어려운 것 같군요 ㅠ
추가로 질문이 있는데요 !
1).
핵심인 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
를 풀어보면 dp[i - coins[j]] + 1 에서 dp[i - coins[j]] 의 의미는 i를 만드는데 coins[j]를 사용하면 "발생할 수 있는 경우의수 -1" 이 맞나요?
저기서 +1 해준건 예를들어 i가 5일때 5코인 하나만 쓸 수 있는거를 +1 해서 포함시켜준거고
dp[i - coins[j]] 이 부분만 따지면 그 +1을 뺀 나머지 경우 ( 11111, 122, 1112 ) 만 포함되는게 맞나요?

2). 그리고 구했던 누적합을 활용해서 식이 돌아가는 건 알겠는데 어떻게 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); 를 세우는 걸까요?
질문이 좀 추상적인데 백지상태에서 이 식을 세우라고 하면 절대 못세울 것 같습니다 ㅠ 그냥 기계적으로 이해하고 암기해도 되는부분일까요?