[백준] 평범한 배낭 (DP)_12865_자바
개발/DS&Algorithms
/ 2022. 7. 3.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 백준의 문제 풀이를 포스팅하려고 합니다. 12865번에 해당하는 문제로, 동적 계획법의 대표적인 문제인 평범한 배낭입니다. 자세하게는 배낭 안에 어떤 물건들을 넣었을 때 최고의 가치를 갖는지 알아보는 문제입니다. 이러한 배낭 문제는 풀이법이 두 가지로 나뉩니다. 첫 번째는 물건을 쪼갤 수 있다고 가정했을 때입니다. 이때는 gready(탐욕) 알고리즘을 통해서 최적의 방법을 찾을 수 있습니다. 두 번째는 물건을 쪼갤 수 없을 때 사용하는 풀이 전략인 동적 계획법 전략입니다. 두 번째 풀이가 오늘 설명할 방식이죠. 이제 문제를 보면서 자세하게 설명하도록 하겠습니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배..
[백준] 평범한 배낭 (DP)_12865_자바
개발/DS&Algorithms
/ 2022. 7. 3.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 백준의 문제 풀이를 포스팅하려고 합니다. 12865번에 해당하는 문제로, 동적 계획법의 대표적인 문제인 평범한 배낭입니다. 자세하게는 배낭 안에 어떤 물건들을 넣었을 때 최고의 가치를 갖는지 알아보는 문제입니다. 이러한 배낭 문제는 풀이법이 두 가지로 나뉩니다. 첫 번째는 물건을 쪼갤 수 있다고 가정했을 때입니다. 이때는 gready(탐욕) 알고리즘을 통해서 최적의 방법을 찾을 수 있습니다. 두 번째는 물건을 쪼갤 수 없을 때 사용하는 풀이 전략인 동적 계획법 전략입니다. 두 번째 풀이가 오늘 설명할 방식이죠. 이제 문제를 보면서 자세하게 설명하도록 하겠습니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배..