[컴퓨팅사고력] 1.4kg을 채울 수 있는 가방에 최대 가치를 찾아 보자.

원당이는 동생과 같이 숨바꼭질을 하다가 창고에서 보물지도를 발견하였습니다.

원당이는 동생과 함께 자신의 가방을 가지고 보물찾기에 나섰습니다.

원당이의 가방은 최대 1400g을 채울 수 있는 가방입니다. 무게를 초과하면 가방의 끈이 떨어져서 가방을 사용 할 수 없게 됩니다. 이때 가방이 자유자재로 늘어나는 소재라서 부피는 관계가 없이 담을 수 있습니다.

보물이 있는 동굴에 들어서니 다음과 같은 보석들이 있습니다.

• 한덩어리가 200g 인 루비는 가치가 40만원입니다.
• 한덩어리가 500g 인 비취는 가치가 110만원입니다.
• 한덩어리가 1kg인 다이아몬드는 가치가 200만원입니다.
• 한덩어리가 300g 인 금은 가치가 50만원입니다.

위와 같은 보석들이 쌓여 있는데 원당이는 어떤 조합으로 가지고 나올때 최대가치는 얼마입니까?

문제풀이

가장 쉽게 접근 할 수 있는 방법은 가치가 최대로 큰 200만원짜리 다이아몬드를 선택 하는 것입니다. 1kg 을 선택후 400g이 남으니 300g인 금을 선택하거나 200g의 루비를 2개 선택하는 방법이 있습니다. 이렇게 선택하게 되면 최대 280만원의 가치를 찾을 수 있습니다. 하지만 잘 생각해 보면  500g 비취 2개 220만원 + 200g 루비 2개 80 만원으로 300만원의 가치를 찾을 수 있음을 발견할 수 있습니다.

 

컴퓨팅 사고력

문제풀이 접근법에서 가치가 큰 200만원짜리 부터 담는 방법은 컴퓨팅 과학에서는 그리디알고리즘 또는 욕심쟁이기법이라고 합니다. 

자신의 순서에서 가장 좋은 것을 취한다고 해서 욕심쟁이 기법이라고 하는데요~

욕심쟁이 기법은 N개의 자료가 있다고 하면 N번만 수행하면 결과를 도출 할 수 있기 때문에 굉장히 빠른 알고리즘이지만 아쉽게도 위와 같은 경우 근사값은 기대할 수 있지만 정확한 값을 찾을 수가 없었습니다.

그리디 알고리즘은 이와 같이 정확하게 값을 찾아 낼 수 있는지를 먼저 확인하고 설계를 하면 되는데요~

위와 같은 문제는 동적계획법(Dynamic Algorithm)을 이용해서 해결을 해 주어야 합니다.

 동적계획법은 그 이전에 계산한 값을 이용하여 다음 절차에서 사용하는 알고리즘입니다.

위와 같은 경우 루비만 있다고 가정을 하면 1400g 에서 200만원의 가치를 담을 수 있습니다.

여기에 비취가 있다고 하면 비취는 500g 이므로 루비를 담은 가방에서 500g을 비우고 비취를 담아 봅니다. 그렇게 해서 더 좋은 가치를 취하게 되면 위와 같이 300만원의 가치를 담을 수 있는 것을 확인 할 수 있습니다.

다이아몬드 역시 1kg 이므로 그 이전에 담아 놓았던 기준에서 1kg 을 비우고 다이아몬드를 담아 보는 형식으로 해서 더 좋은 가치를 찾아 보면 됩니다.

이렇게 하면 모든 경우를 다 계산해 볼 수가 있으면서 그 이전에 계산했던 내용을 기준으로 계산하기 때문에 빠르게 계산을 할 수가 있습니다.