침몰하는 타이타닉 문제 질문입니다
56
2 asked
최적 값을 보장하지 않음에도 최소 개수를 출력 가능한 이유가 궁금합니다.
예를 들어 10 20 80의 경우 80+10/ 20 이나 80+20/10이나 결국엔 2개의 보트가 필요한 건 같고 낭비 공간의 총량도 동일합니다.
하지만 자꾸 돌아보면 최적 값으로 맞추는 로직이 추가 되어야 하지 않을까? 라는 의문이 남습니다.
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다. 고건님.
업계에서 “침몰하는 타이타닉 문제”로 많이 알려져 있는 이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다. 이 알고리즘은 항상 최적의 해를 보장하지는 않지만, 주어진 조건 하에서 더 효율적으로 문제를 풀 수 있는 방법을 제시합니다.
이 문제에서는 무거운 승객과 가벼운 승객을 한 쌍으로 묶어 무게 제한을 최대한 잘 활용하는 방법으로 보트의 개수를 최소화합니다. 예를 들어, 주어진 승객의 무게가 10, 20, 80일 때, 80과 10을 묶어 한 보트에 태우고, 20을 다른 보트에 태웁니다. 이는 무게 제한을 최대한 사용하여 보트의 개수를 최소화하는 방법입니다. 실제로, 그리디 알고리즘은 반드시 최적의 솔루션을 제공하는 것은 아니지만, 주어진 제한 내에서 효과적인 결과를 제공한다는 점에서 유용할 수 있습니다.
또한, 이 문제에 대한 다양한 방법론에 대한 이해를 원하신다면 아래의 관련 질문들을 참고해 보세요:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
0
76
2
스택에서 ')'을 만나는 경우
0
78
3
문제가 어디있나요?
0
65
2
변수 or 함수명
0
61
1
AA.py 책점 에러
0
57
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
160
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
163
2
동적계획법은 사용하는 문제
0
126
2
제 코드 좀 봐주세요
0
148
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
114
0
오류원인?
0
98
0
리스트 선언
0
106
1
침몰하는 타이타닉(그리디) 문제 질문
0
109
1
알고리즘
0
69
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
126
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1
섹션 9 Dynamic Programming (동적 계획법) 최대부분증가수열
0
116
2