재귀로 n 번 돌고 각 재귀에 두 가지로 갈라진다면 2ⁿ 가지의 경우를 따지게 될 것 같습니다.
1495번 - 기타리스트
재귀로 n 번 돌고 각 재귀에 두 가지로 갈라진다면 2ⁿ 가지의 경우를 따지게 될 것 같습니다.
일단 gemini에게 물어봐서 해결하기는 했습니다
직접 푼건 아니라서 해결이라고 하기는 좀 그렇긴 하죠...
gemini에게 물어본 결과 재귀 방식으로 메모이제이션을 이용해서 잘 풀었다고 칭찬은 받았습니다. 논리적으로 전혀 문제가 되지 않는 코드라네요
하지만 재귀를 사용해 푸는것 자체가 문제였다고 합니다
1. 함수를 호출하고 반환하는 과정에서 오버헤드가 발생하는데 한 두번이면 괜찮은데 최대 50번까지 반복 한다면 무시하지 못할 정도로 느려진다네요
2. 캐시 메모리 효율도 재귀보단 for문이 더 좋다고 하네요 (이건 메모리 초과 문제 아닌가..?)
근데 지금까지 dp문제를 전부 재귀로 풀고 있어서 50번 이상인 것도 분명히 풀었을 것 같은데 왜 여기서만 이러는지는 잘 모르겠네요
몇가지 테스트를 더 해봐야 알 것 같습니다
댓글을 작성하려면 로그인해야 합니다.
chan00106 1년 전
제귀로 n번 만큼 돌게 만들었고, 각 케이스 마다 더하거나 빼는 2가지의 경우밖에 없으니 시간 복잡도는 n2이 되는게 맞지 않나요?(시간복잡도 계산할 줄 모름)
근데 메모라이즈를 통해서 50번 으로 연산할 수 있게 줄어든거고요 (n의 최대 값이 50)
그럼 시간초과가 없어야 하지 않나요...?
dp 고수분 도와주세요ㅠㅜ