오랜만에 사회에서 풀어보는 문제이다. 확실히 코딩 문제 푸는 기간을 오래 쉬었던만큼 부족한 부분이 많이 느껴졌고. 어떤 문제를 올릴까 고민을 많이 했는데 이 문제가 되게 좋은 문제라는걸 느껴서 올리고싶었다. 예전에 한참 고민을 많이 했었던 2022 SK ICT Family 때 나온 첫번째 코딩 문제와 굉장히 유사했었고. 만약에 내가 이 문제를 그때 풀어봤다면 정말로 쉽게 풀었을수도 있겠다 생각이 들었다.
이 문제의 풀이를 나는 항상 DP 방식으로 밖에 풀수있겠다 라는 고정 생각이 있었는데 태그에 BFS로도 풀수있단걸 본 순간 어떻게 하지 고민을 많이 했는데 내 첫 시도에는 보기좋게 실패했고 다른 사람의 풀이를 참고해서 새로운 방법을 배웠다.
첫번째 시도에서 완전 접근 자체가 틀렸던 문제. Greedy 처럼 접근해서 가장 가치가 높은 화페부터 pq를 사용해 풀까 싶었지만 동전의 조합을 찾아야하는 문제인데 이렇게 사용하는거 자체가 틀린 방식이었다.
내가 이 문제를 보면서 깨달은 점은. BFS에 활용도이다. DFS만이 완전탐색이 아니고 BFS또한 완전탐색의 일부이다. 만약에 BFS를 할때 priority_queue 가 아닌 그냥 queue 를 사용했다면 그것은 모든 가능성을 파악하고자 쓰는것이다. 동전을 넣으면 되나 하고 생각했던 내 방법은 틀렸고 결국 amount를 넣어서 점차 정답을 찾아냈다.
그리고 여기서 중요한 점은 unordered_set 를 사용했단점. set의 활용법은 만약에 이미 계산된 amount가 있다면 더 이상 계산하지 말자는 것이었다. 이게 내가 배운 새로운 방법, 즉 memorization 을 bfs에 넣는 방법이다. 물론 이 방법의 활용도를 언제 사용할지 모르지만 만약에 저 set부분을 뺐다면 TLE 가 나와서 얼마나 중요한 부분인지 알았다.
결론적으로 만약에 queue 안에있는 amount가 해당 값에 도달했을때는 바로 리턴해주면 그게 최소값이었다.
(TOP-DOWN)
(BOTTOM-UP)
마지막으로는 memorization 을 활용한 dfs 서치 방법이다. 이 문제는 돌이켜 생각해보면 구종만의 책에서 배웠던 knapsack 문제와 굉장히 유사한 문제였고. 여기서 활용한 dfs 방식으로는 같은 코인을 여러번 챙기느냐 아니면 그 코인을 포기하고 다른 코인을 선택하냐의 차이점이었다. 내가 지금까지 memorization을 활용한 dp문제들을 풀어보았을떄 결국은 두가지의 선택지인거같다. 이걸 가져가냐 아니면 냅두냐. 그 점에서 memorization을 얼마나 잘 활용하냐가 문제인거같은데 나 같은경우는 아직도 너무 부족한거같다. 더 많이 풀어보고 기록도 더 많이 남겨놔야지 공부가 좀 될거같다.
배운점:
1. Memorization을 활용한 BFS 방법
2. Knapsack problem의 정석.
