• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

냅색 12865 시간초과

24.04.18 16:03 작성 24.04.18 16:03 수정 조회수 139

1

심화>최적화(재귀, 백트래킹의 경우의 수) 강의 4번문제를 풀었는데, 백준에 제출하면 계속 시간초과가 뜨네요..!

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)]

value = 0
def recur(idx, tw, tv):
    global value
    if tw > k: # 무게 초과
        return
    
    if idx == n:
        value = max(value, tv)
        return

    recur(idx+1, tw+stuff[idx][0], tv+stuff[idx][1])
    recur(idx+1, tw, tv)

recur(0, 0, 0)
print(value)

수업자료를 참고하고 싶은데, mp4로 올라와있어서 질문 남깁니다.
시간초과를 어떻게 하면 피할 수 있을까요?

답변 2

·

답변을 작성해보세요.

0

강의 자료 업데이트 해뒀습니다! 혼란을 드려서 죄송해요 ㅠㅠ!

 

냅색은 백트래킹으로 백준문제가 안풀립니다! 식은 정확하세요 :)!!

 

백준의 냅색 문제는 해당 코드를 조금 더 개선시켜서 메모이제이션을 추가해서 다이나믹 프로그래밍 코드로 바꾸면 풀리게 됩니다! ㅎㅎ 다음 강의를 이어서 들어주시면 됩니다!

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.04.18

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

서바리바리 님께서 질문하신 냅색 문제(12865)에 대한 시간 초과 문제 해결 방법을 찾으시는군요. 먼저, 시간 초과 문제는 주로 비효율적인 알고리즘 구조 때문에 발생합니다. 냅색 문제 같은 경우, 재귀 함수만을 사용하여 모든 가능한 조합을 탐색하는 것은 큰 입력값에서 매우 비효율적일 수 있습니다. 따라서 최적화할 필요가 있습니다. 동적 프로그래밍(Dynamic Programming, 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 배열에 저장함으로써 중복 계산을 줄이고 시간 초과 문제를 방지합니다.

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

채널톡 아이콘