huiyu's blog

배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데, 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다. 쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다. -> 위키백과 냅색 문제는 아래 링크에서 풀어 볼 수 있습니다. ->0/1 Knapsack 문제 보러가..

1. 동적 계획법(Dynamic Programming)이란?분할 정복과 같은 접근방식을 갖고 있습니다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 차이가 발생하는 부분은 문제를 나누는 방식입니다. 부분문제가 여러번 사용될 수 있을 때 여러번 중복 계산하는 것이 아닌, 한번만 계산하고 저장해둬 재활용해 사용합니다. (a)서로 연관이 없는 부분문제 (b)서로 의존하고 있는 부분문제 (a)는 서로 연관이 없어 단순히 재귀 호출을 통해 문제를 풀어도 한 부분문제를 한 번만 해결합니다. (b)는 부분문제가 서로 의존하고 있어, 단순 재귀로 풀면 중복 계산이 많아집니다. 예를 들면 cde는 abcde를 해결할 때, cdef..