chan00106   1년 전

제귀로 n번 만큼 돌게 만들었고, 각 케이스 마다 더하거나 빼는 2가지의 경우밖에 없으니 시간 복잡도는 n2이 되는게 맞지 않나요?(시간복잡도 계산할 줄 모름)

근데 메모라이즈를 통해서 50번 으로 연산할 수 있게 줄어든거고요 (n의 최대 값이 50)

그럼 시간초과가 없어야 하지 않나요...?

dp 고수분 도와주세요ㅠㅜ

sianke1991   1년 전

재귀로 n 번 돌고 각 재귀에 두 가지로 갈라진다면 2ⁿ 가지의 경우를 따지게 될 것 같습니다.

chan00106   1년 전

음 2n 이군요

근데 지금 dp를 사용해서 i번째 곡과 p(현재 볼륨)을 가지고 메모라이즈를 하고 있는데 이래도 자꾸 65%에서 시간 초과가 발생합니다 

다른 곳에서 -1의 의미가 중복돼서 모든 경우를 탐색하게 되고, 그걸로 시간 초과가 발생할 수 있다라는 글이 있어서 초기값을 -2로 변경했지만 그래도 시간 초과가 발생하네요

진짜 뭐가 문제인지 전혀 모르겠습니다...

chan00106   1년 전

일단 gemini에게 물어봐서 해결하기는 했습니다
직접 푼건 아니라서 해결이라고 하기는 좀 그렇긴 하죠...

gemini에게 물어본 결과 재귀 방식으로 메모이제이션을 이용해서 잘 풀었다고 칭찬은 받았습니다. 논리적으로 전혀 문제가 되지 않는 코드라네요

하지만 재귀를 사용해 푸는것 자체가 문제였다고 합니다
1. 함수를 호출하고 반환하는 과정에서 오버헤드가 발생하는데 한 두번이면 괜찮은데 최대 50번까지 반복 한다면 무시하지 못할 정도로 느려진다네요
2. 캐시 메모리 효율도 재귀보단 for문이 더 좋다고 하네요 (이건 메모리 초과 문제 아닌가..?)


근데 지금까지 dp문제를 전부 재귀로 풀고 있어서 50번 이상인 것도 분명히 풀었을 것 같은데 왜 여기서만 이러는지는 잘 모르겠네요
몇가지 테스트를 더 해봐야 알 것 같습니다

bluemary   1년 전

만약 getMaxVolume(v,i) 계산할 때

1) if (v+p[i]<=m)
2) if (v-p[i]>=0)

이 두 조건문 모두 안걸리면 ret이 -2로 남게 되는데

이러면 다음에 getMaxVolume(v,i)를 호출했을 때 cache[i][v]는 캐시 되지 않은 것으로 판정되서(cache[i][v] == -2이므로) 또 다시 계산하려고 들기 때문인 것 같네요.

댓글을 작성하려면 로그인해야 합니다.