7-U 1450 냅색문제 메모리 초과 질문

작성한 질문수 19

2

안녕하세요 종현님 ㅎㅎ

그런 자세는 정말 너무 좋습니다. 열심히 고민하셨네요. ㅎㅎ

여쭤보고 싶은 것이 강의에서 'DP로 풀면 상태값 저장하기가 힘들다'라는 말씀해주셨는데 혹시 이 말뜻이 구체적으로 무엇을 뜻하는건가요?

>> 이게요

N개의 물건을 가방에 넣는 방법의 수

를 구하는 문제이며

N은 30보다 작거나 같은 자연수, C는 10^9보다 작거나 같은 음이 아닌 정수

이잖아요.

여기서 DP로 만약에 푼다면 상태값을 저장해야되요.

상태값을 생각할 때 dp[c] = x라는 남은 무게가 있을 때의 경우의 수라고 놓을 수 있어요.

dp[c]를 정의하고 c일 때 몇개의 경우의 수를 기반으로도 구축하는 것을 생각할 수 있어요. 이때는 10억개의 배열이 필요합니다. 공간복잡도가 초과하게 되겠죠.

근데 이것도 c를 기반으로 하게 되면 DAG를 만들어서 한다 하더라도 중복되는 c가 발생했을 때의 그 때의 최적해값으로 갱신하는게 아니라 경우의 수이므로 더해야 하는것이기 때문에 dp[c]를 정의하는 것 자체가 힘들 수 있어요. 메모이제이션 자체가 힘든 것이죠. 예를 들어 1번째, 2, 5번째를 포함한 c가 10이라고 했을 때 해당 경우의 수가 2이고 1, 3, 6을 포함한 c가 10이라고 했을 때 해당 경우의 수가 10이라고 한다면 +를 하면 12가 되는게 자명한데 메모이제이션쓰게 되면 2 + 2 이런식으로도 할 수 밖에 없어서.. 메모이제이션 자체도 힘든 단점이 있습니다.

즉, 상태값을 저장한다해도 공간복잡도 초과에다 dp 메모제이션 구현도 힘들어서..

dp는 적합한 알고리즘이 아니며 meet in the middle이 적합한 알고리즘이 되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.