냅색 12865 시간초과

안녕하세요, 인프런 AI 인턴입니다.

서바리바리 님께서 질문하신 냅색 문제(12865)에 대한 시간 초과 문제 해결 방법을 찾으시는군요. 먼저, 시간 초과 문제는 주로 비효율적인 알고리즘 구조 때문에 발생합니다. 냅색 문제 같은 경우, 재귀 함수만을 사용하여 모든 가능한 조합을 탐색하는 것은 큰 입력값에서 매우 비효율적일 수 있습니다. 따라서 최적화할 필요가 있습니다. 동적 프로그래밍(Dynamic Programming, DP)을 사용하여 중복 계산을 최소화하는 방법을 고려해보시길 추천드립니다.

이와 관련하여, 제가 찾은 기존 답변은 다음과 같습니다:

“12865 배낭문제”에서는 탑다운 다이나믹 프로그래밍(DP)과 메모이제이션을 활용한 접근 방식을 설명합니다. 메모이제이션은 이미 계산된 결과를 저장하여 중복 계산을 방지하는 기법으로, 시간 복잡도를 크게 줄일 수 있습니다.
또한, “최적화(재귀, 백트래킹의 경우의 수 ) 마지막 문제(냅색) 코드에 질문이 있습니다.”에서 다루는 질문은 재귀를 활용한 냅색 문제 해결 시, 주어진 코드 내에서 발견된 오타에 대한 것을 포함하여, 재귀와 백트래킹을 활용한 문제 해결 전략에 대한 추가 정보가 제공됩니다.

위 답변들에서 강조하는 중요 포인트는 재귀 함수를 사용할 때, 이미 검토한 경우의 수에 대한 결과를 저장하는 메모이제이션 기법의 적용입니다. 서바리바리 님의 코드에서는 이 기법이 누락되어 있어서, 같은 계산을 반복하게 되고 이로 인해 시간 초과가 발생할 가능성이 높습니다.

다음과 같이 서바리바리 님의 코드에 메모이제이션 기법을 적용해볼 수 있습니다:

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, k = map(int, input().split())
stuff = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1 for _ in range(k+1)] for _ in range(n+1)]

def recur(idx, tw):
    if idx == n:
        return 0
    if dp[idx][tw] != -1:
        return dp[idx][tw]
    
    # 물건을 넣지 않는 경우
    result = recur(idx+1, tw)
    # 현재 무게에서 물건을 넣을 수 있는 경우
    if tw + stuff[idx][0] <= k:
        result = max(result, recur(idx+1, tw+stuff[idx][0]) + stuff[idx][1])
    dp[idx][tw] = result
    return result

print(recur(0, 0))

위 코드 예제는 메모이제이션을 포함하고, 재귀 호출을 통해 각 단계에서의 최적의 값을 dp 배열에 저장함으로써 중복 계산을 줄이고 시간 초과 문제를 방지합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변