자연계열 2번

[가] 상점에서 카운터를 보고있는 철수는 손님에게 동전만을 이용하여 거스름돈을 주어야 하는 상황이 종종 있다. 하지만 손님은 동전을 많이 받는 것은 보통 좋아하지 않는다. 예를 들어 거스름돈이 870원인 경우, 10원짜리 동전 87개를 주면 아마 거의 모든 손님은 화를 낼 것이다. 따라서 철수의 ‘거스름돈 문제’는 동전을 합하여 거슬러 줄 액수가 되면서 동전의 개수가 최소가 되는 동전의 집합을 찾는 것이다. 같은 단위 가치의 동전들은 서로 다른 동전들로 취급한다. 각 단위의 동전 개수가 무한이 많다고 가정할 때 이 문제를 어떻게 단계별로 풀어야 할까?철수는 다음의 방법론을 생각하였다. 거스름돈을 비어있는 집합으로 시작한다. 즉 거스름돈의 총액은 0원이다. 그리고 가치가 가장 높은 동전을 찾는다. 어느 동전이 가장 좋은지를 결정하는 기준은 동전의 단위 가치가 된다. 이 단계를 ‘탐욕적 선택 과정’이라고 하였다. 다음 이 동전을 현재 거스름돈의 총액에 더한 후의 거스름돈의 총액이 거슬러주어야 할 액수를 초과하는지 본다. 이 단계를 ‘적정성 검증’이라고 하였다. 만약 이 동전을 추가한 거스름돈의 총액이 거슬러 주어야 할 액수를 초과하지 않으면, 그 동전을 거스름돈에 넣는다. 그 다음 거스름돈의 총액이 거슬러 주어야 할 액수와 같은지 알아본다. 이 단계를 ‘해답 점검’이라고 하였다. 만약 같지 않다면, 다시 선택 과정을 통해서 다른 동전을 찾고, 다음 단계의 과정을 되풀이 한다. 거스름돈의 총액이 거슬러 주어야 할 액수와 같으면 이 과정을 종료한다.철수의 문제 풀이 방법은 ‘탐욕적’이다. 왜냐하면 선택 결정 단계에서 선택된 동전이 발생시킬 수 있는 잠재적인 추후의 결점을 전혀 고려하지 않고, 선택 당시 최고로 비싼 동전을 단순히 ‘탐욕적’ 방법으로 선택하기 때문이다.

[나] 어떤 도둑이 한 보석상에 배낭을 메고 침입했다고 하자. 훔친 물건의 총 무게가 배낭의 용량 $\displaystyle W$를 초과하면 배낭이 망가진다. 각 물건의 값어치와 무게는 알고 있다고 한다. 이 밤손님의 ‘배낭 문제’는 총 무게가 $\displaystyle W$를 초과하지 않으면서 물건의 총 값어치가 최대가 되도록 물건을 배낭에 담는 것이다. 물건은 쪼개어 담을 수 없다. 도둑의 친구A와 친구B는 각자 도둑에게 이 문제를 풀기 위해서 윗글 [가]에서 설명하는 문제 풀이 방법론을 적절히 적용하면 된다고 하였다. 하지만 두 친구의 ‘탐욕적 선택 과정’ 단계에 이견이 있다.

[다] 미용사 영희에게 여러 가지 다른 종류로 머리를 하려고(예를 들어 커트, 커트/샴푸, 파마, 염색) 동시에 미용실에 와서 기다리고 있는 손님들이 있다고 가정해 보자. 머리를 하는 종류별로 걸리는 시간이 서로 같지는 않지만, 영희는 각각 얼마나 걸릴지 알고 있다. ‘스케줄짜기 문제’는 손님들이 기다리고 서비스 받는데 소요되는 총 시간이 최소가 되도록 손님들을 서비스하는 스케줄을 짜는 것이다. 예를 들어 손님 A, B, C가 있고, 각 손님이 원하는 작업을 하는 데 5, 10, 4시간이 걸린다고 하자. 만약 A, B, C의 순서로 스케줄을 짠다면, 작업 세 개를 완료하는데 걸리는 총 시간은 $\displaystyle 5+(5+10)+(5+10+4)=39$시간이다. B, C, A로 짠다면 $\displaystyle 10+(10+4)+(10+4+5)$의 총 43시간이다.