라면공장 알고리즘 힙문제풀이, 섬머코딩 후기

 

 

 

---

2019 섬머코딩 참여 후기

최근 섬머코딩에 참여해서 2문제를 겨우 풀고 마쳤습니다.. 앞의 문제는 쉬운문제였는데도 당황하고 머리가 쌔-하얘짐을 느꼈습니다. 너무너무 오래걸렸어요! 허무함도 느꼈구요. 살짝 내용이 달라지면 이렇게 멈칫하고 못풀게 되는구나... 제 실력에 매우 회의감이 들더군요.

A라는 알고리즘 문제를 한번 풀었다고 그 문제가 자신의 것이 될까요? 그 문제를 일주일뒤, 심지어 몇일 후에 보시면 다시금 전전긍긍하고 머리가 하얘지는경우가 많으실겁니다.

비슷한 유형 문제들에대해서도 거리낌없이 풀어낼 수 있을 정도는 되어야(자다깨서 갑자기 풀어도 뚝딱 풀정도의 수준은 되야..) 그 유형의 문제에 대한 숙련도가 어느정도 쌓였다고 볼 수 있지 않을까 싶습니다. (복습이 답인 듯 ㅠ.ㅡ..) 그런 제 생각을 이번 섬머코딩 참여로 더 느꼈네요. 좋은 경험이었습니다.

음.. 요즘도 매일매일 문제를 하나 둘 풀어가고, 그렇게 풀어낸 문제수는 늘어나지만, 그 성장세가 당장 크게 느껴지진 않습니다. 이전 문제들을 다시 풀어보면 긴가민가한경우가 절반은 될 겁니다. 이렇게 성장이 더디지만 한번 발을 내딛고 나니 욕심이 나네요. 대학시절에 이 재미를 좀 알아야 했는데. 하는 생각이 항상 들지만 이제 후회한들 뭐하겠습니까! ^~^;;

 

 

---

• 알고리즘문제, 라면공장 풀이

오늘은 라면공장 문제를 풀어봤네요. 프로그래머스 고득점 킷의 힙 문제 1,2번째 둘다 우선순위큐로 풀어낼 수 있었습니다. 넣은 값에 대해 오름차순정렬, 혹은 내림차순정렬을 알아서 시켜주는 우선순위 큐는 매우 유용합니다.

 

라면공장문제는 현재 밀가루재고(int stock), 추가밀가루공급가능일(vector<int> dates), 공급가능일 별 공급가능한 밀가루량(vector<int> supplies), 밀가루공급해야하는 일수(int k)를 참고해서 최소로 밀가루 공급을 받는 횟수를 결과로 출력하는 힙(Heap) 응용문제였습니다.

매일 밀가루는 1씩 감소합니다.(stock--;) 밀가루재고가 도중 부족해지는 경우는 없도록 입력값이 나옵니다.

이 문제의 핵심은 밀가루를 공급해야하는 총 일수, k기간동안 최대한 공급을 적게 받아야 하는 것입니다. 그러기 위해서

* 밀가루가 0개가 되기 전까지 최대한 가능한 추가밀가루공급기회를 저축해야합니다. * 밀가루가 0개가 되었을때 시점 기준 제일 효율적으로 밀가루를 공급 받을 수 있어야 합니다.

예를들어 stock 10, dates [1,8,10], supplies [1,1,100], k=100의 상황이 있다고 가정합니다. 

1, 8, 10일에는 각각 1, 1, 100개의 밀가루를 총 최대 3번 공급받을 수 있습니다. 그러나 이렇게 3번 공급을 받으면 굉장히 비효율적입니다. 차라리 밀가루 재고stock이 바닥나기 직전인 100일차에 100개의 밀가루 공급을 단 한번만 받고 끝낼 수도 있기 때문입니다. 

 

 

 

---

• 우선순위 큐(priority_queue)의 사용

이 목표를 달성하기 위해서 우리는 우선순위 큐를 사용할 수 있습니다. 

1) priority_queue<int, vector<int>, less<int>> queue; 를 선언합니다.

2) 공급가능한날에 도달하면 현재 공급가능한 밀가루량을 사용해서 queue.push(공급가능일이 되면 해당 공급가능일에 공급받을 수 있는 밀가루량); 해줍니다. (공급량, supplies[i] 사용 후, i++로 다음 공급가능한 날을 비교할 준비를 한다.)

우선순위큐, queue.top()은 현재 우선순위 큐 데이터의 최댓값을 나타내므로 stock(밀가루 재고량)이 바닥날시점에 현재시점에서 가장 많이 공급받을 수 있는 밀가루의 양을 판단할 수 있게 됩니다. stock 밀가루 재고량이 바닥날때, queue.top()를 활용하여 재고량을 채우고, 사용한 queue Data는 pop(); 시킵니다. 

 

---

 

 

그렇게 되면 힙문제, 라면공장에서 요구하는 최소 밀가루 추가공급횟수를 알 수 있습니다. 오늘은 이렇게 프로그래머스의 힙문제 풀이도 두서없이 정리해보고 섬머코딩 후기까지 남겨봤습니다.

음.. 결론은 좀더 분발해야겠습니다. 개발관련분야에 발을 들인 이상, 꼭 고수가 되고싶네요. 화이팅!