침몰하는 타이타닉(그리디) 문제 질문

안녕하세요! 강의 잘 듣고 있습니다

공부를 하다가 오래 고민해도 이해가 안되는 부분이 생겨서 질문 처음 남겨봅니다~

침몰하는 타이타닉 (그리디) 문제에서 예를 들어

무게가 100 90 80 80 80 80 40 30 20 10 인 10명의 사람들을 무게 한도가 140인 구명보트에 태울때

강사님 풀이 대로면 100인 사람과 10 인 사람을 태우고

90 인 사람과 20인 사람을 태우는 방식으로 시작해서

(100,10) (90,20) (80,30) (80, 40) (80) (80) 이렇게 6개의 구명보트에 사람을 태우는데

저는 100인 사람과 40인 사람을 먼저 태워야한다고 생각을 했습니다.

뭔가 강사님 풀이대로 100인 사람과 10 인 사람을 먼저 태우면 80 인 사람이 혼자 타게 되는데

100이 40과 함께 타면 80 인 사람이 10 인 사람과 같이 탈 수 있으니 80은 혼자 타지 않아도 되서 cnt 가 최소가 되는게 아닌가 생각했습니다.

( 즉 100 일떄 140 - 100 은 40 이니 40보다 작은 수 중에서 가장 큰 값을 구하는 방식으로 풀었습니다 이중 반복문을 사용합니다 (100, 40) (90, 20) (80, 20) (80, 10) (80) (80) )

제가 제 방식, 강사님 방식으로 5시간정도 시뮬레이션 해 본 바로는 결국 결국 cnt는 같았습니다

그런데 왜 같은지 논리적으로는 이해할 수가 없어요.. ㅠㅠ

논리적으로 왜 같은지 혹시 설명해주실 수 있으실까요..

안녕하세요, 이자영님. 인프런 AI 인턴입니다.

그리디 알고리즘은 선택을 할 때마다 가장 최적이라고 생각되는 선택을 하는 알고리즘입니다. 특정 문제에서 항상 최선의 결과를 보장하는 것은 아니지만, 그리디 알고리즘이 동작하는 문제에서는 일반적으로 복잡한 계산 없이 빠르게 답을 찾을 수 있습니다.

지금 질문하신 “침몰하는 타이타닉” 문제의 경우, 그리디 알고리즘을 사용하여 가장 무거운 사람과 가장 가벼운 사람을 함께 태우는 방식으로 해결합니다. 이 방식은 결과적으로 남은 사람들을 가장 작은 수의 구명보트에 태워 구조할 수 있음을 보여줍니다.

자영님이 우려하신 예제에서, 왜 특정 케이스에서 최적의 조합이 되지 않게 해결되는 것처럼 보이는지 설명드리겠습니다:

두 가지 방식 모두 최적: 문제에 주어진 특성상, 최적의 해결법은 몇 가지 형태가 있습니다. 예를 들어, 가장 무거운 사람과 그다음으로 무거운 사람들을 먼저 처리하면서 무게 제한 내에 맞추는 방식은 구명보트의 이용 횟수를 최소로 하는 방향으로 이어질 수 있습니다. 이 구체적인 문제에서는 두 방법 모두 거의 비슷한 수준의 성능을 보여주기에 그리디 해법이 유용하며 간단한 해결책이 됩니다.

결국 두 알고리즘이 동일한 해답을 도출하는 이유는 주어진 상황과 제한 조건 내에서 가능한 최적의 조합을 여러 방법으로 찾아갈 수 있기 때문입니다. 이 과정에서 두 방식이 자연스럽게 교차하게 되고, 비슷한 효율성을 갖게 됩니다.

아래의 링크에서 유사한 질문과 해설을 참고하실 수 있습니다:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변