백준 12865문제 질문드립니다.
그리디 연습문제 및 목표 문제 중에 12865번 평범한 배낭 문제가 있던데 그리디로 풀 수가 있나요? 최적의 해가 전체 최적해를 보장하지 않는데.. dp로만 풀리는 문제가 아닌가 해서 질문드립니다.
Câu trả lời 2
0
안녕하세요, 인프런 AI 인턴입니다. 김규혁님.
질문해주신 백준 12865번 “평범한 배낭 문제”에 대해 설명드리겠습니다. 이 문제는 오해하기 쉽지만, 그리디 알고리즘으로는 해결할 수 없는 전형적인 배낭 문제입니다. 일반적으로 0/1 배낭 문제로 불리며, 이 문제를 해결하기 위해서는 동적 계획법(Dynamic Programming, DP) 접근법을 사용해야 합니다.
핵심 설명:
- 그리디 접근이 불가능한 이유: 그리디 알고리즘은 현재 단계에서 최적의 선택을 하는 방법이지만, 이 문제는 물건의 부분적인 선택이 불가능합니다. 즉, 물건을 쪼갤 수 없음을 고려해야 하기 때문에 그리디 알고리즘이 적합하지 않습니다.
- DP 접근법: 주어진 물건과 최대 무게에 따라 물건의 조합을 변형하여 최대 가치를 얻는 방법입니다. 2차원 배열을 사용하여 물건을 한 개씩 고려하며, 각 단계에서 최대 가치를 갱신하게 됩니다.
이미 여러 학생들이 이 문제에 대해 학습하며 어려움을 겪고 있으며, 이를 해결하기 위한 다양한 전략과 코드를 논의한 게시물들이 있습니다. 특히 관련 문제를 다룬 기존 답변을 참고하시면 구체적인 코드와 해법에 대해 더 명확히 이해하실 수 있습니다. 아래 링크에서 DP를 이용한 해결 방법과 관련된 토론을 참고하시기 바랍니다.
- 백준 12865 문제 관련 토론 및 답변: 이 링크에서는 비슷한 문제에 대해 수많은 수강생들이 질문하고 해결 방안을 찾기 위한 방법들이 논의되고 있습니다.
차후 질문이 있으시면, 마음껏 이어서 문의해 주세요. 추가적인 설명과 코드를 제공할 수 있도록 노력하겠습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
예시1 질문
0
50
1
안녕하세요 코테 난이도
-1
334
2
연습문제 답 제공 관련하여
0
74
2
코테가 1주일 남았을 때의 학습 우선순위
0
104
2
목표문제
0
82
2
선행으로 공부하면 좋을 이산수학 종류를 알고싶어요.
0
110
1
사전문제가 잘 보이지 않습니다 !
0
81
2
스스로 고민하고 답을 보지 않고 구현을 해보았는데요
0
107
2
섹션 6 사전문제 3번문제 답안이 틀린것 같아요
0
128
2
입/출력으로 모듈화를 해서 문제를 풀어보려고 하는데 방향이 맞는지 궁금합니다.
0
92
1
사전문제말구 수업 강의하실때 사용하시는 자료는 배포안하시나요??
0
118
2
6강 연습문제 13137 질문있습니다.
0
88
1
오류
0
114
2
재귀
0
104
2
1강 연습문제&목표문제 정답지 위치
0
178
2
1강 연습문제 복습문제1 문제 오류
0
102
2
안녕하세요, print 방식에 대해 문의드립니다.
0
102
2
3:30 - sys.stdin.readline 질문
0
99
1
트리 - 목표문제 11725 메모리 초과
0
175
3
사전문제 관련 질문
0
166
2
식 오류 있습니다.
1
137
1
해상도 720p 라 글자가 흐릿하게 보입니다.
0
163
2
대기업 코테 난이도
0
630
1
2강 사전문제
0
199
1