Knapsack 알고리즘(동적 프로그래밍)

Seokwon Han·2020년 11월 10일
0

알고리즘 공부

목록 보기
3/5
post-thumbnail

동적 프로그래밍

동적 프로그래밍의 또 다른 예시로 피보나치 수열이 있는데, 가장 쉽게 생각할 수 있는 재귀함수를 이용해서 문제를 푼다면 그림과 같이 중복되는 부분을 또 재귀함수를 사용해서 값을 얻어야한다.

이는 숫자가 커지면 커질수록 중복되는 계산이 많아지므로 큰 오버헤드를 불러일으킨다.
이 문제에 대한 해결방법으로 동적 프로그래밍은 이전에 계산한 값들을 메모리에 저장해서 반복작업을 줄인다.
따라서 동적 프로그래밍 문제를 풀 때의 키포인트는 계산값을 저장해 둘 배열같은 메모리공간을 미리 할당해놓은 뒤 계산된 값을 저장하면서 필요할때 꺼내쓰는것이다.

문제 설명

배낭 채우기 문제라고 많이 알려진 이 알고리즘은 동적 프로그래밍의 대표적인 문제 중 하나이다.

일정 무게 이하의 보석을 담을수 있는 가방에 보석들을 넣었을 때 배낭에 든 보석들의 가격 총합의 최대값을 구하는 문제이다.

풀이법

다음과 같이 값을 저장해 둘 2차원 배열을 만들고 이를 표로 표현하면 다음과 같다.

행(i)은 보석의 종류(1kg $2, 2kg $3, 3kg $4 4kg $6)를 나타내고
열(w)은 가방의 무게, 엘리먼트의 값은 보석을 넣었을 때 보석의 가치의 합이다.
첫번째 행과 열은 전부 0으로 초기화한다.

구해야 하는건 5kg일때의 최대값이므로 다음과 같은 공식을 적용해서 하나하나 표를 완성하면 된다.

profile
개발하면서 새로 배우거나 경험한 내용을 정리하고 그 외의 공부한 내용을 기록하는 곳입니다.

0개의 댓글