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

안녕하십니까 코딩센세님!

잘 와닿지 않는 부분이 있어서 3일 정도 곱씹어보다가, 제가 생각한 바가 맞는지 검토가 필요해서 추가로 질문을 작성해봅니다.

=====================================

[활용 (바텀업DP)] 강의에서 10:34초 쯤에,
냅색 문제의 탑다운DP 코드 일부분을 가리키며 이렇게 말씀하십니다. "이 재귀함수는 뒤에서부터 채워주는 형태죠?"

Q1. 여기서, 뒤에서 채워준다는게 dp의 값을 idx==N부터 0을 리턴하며 dp[idx]에 값이 채워지기 때문이라고 이해하면 맞을까요?

Q1-1. 위의 질문을 다르게도 표현하자면, 탑다운DP 방식으로 접근했기 때문에 엣지에서 시작하므로 끝에서부터 채워진다고 볼 수 있기 때문일가요?

Q1-3. Q1.에서 이해한 바가 맞다면, 그와 같은 논리를 바탕으로, [활용 (바텀업 DP)] 강의 10:26초에서 설명하신 다음 코드에서 idx 부분을 빼줘야 하는 이유를 이해했지만,

weight에서 item만큼의 무게를 빼줘야 하는 이유가 아직까지 이해가 되 지 않습니다..

dp[idx][weight] = max(dp[idx - 1][weight - items[idx][0]] + items[idx][1], dp[idx-1][weight]

=====================================

[활용 (바텀업DP)] 강의에서 07:22~07:39초인덱스를 초과한 경우에 대한 연산을 설명하시는데요.

Q2. if idx + interview[idx][0] > N:
dp[idx] = dp[idx+1]
위 코드를 가리키시며, "인덱스가 넘는 경우는 그냥 뒤에걸, 선택 안하는거를 추가해준다고 하고.." 라고 설명하셨습니다. 저는 이게 어떤 부분을 의도하시는건지 와닿지가 않았습니다.

바텀업 dp는 코드를 따라가며 종이에 dp테이블을 적어보려 노력해봐도, 이해를 다 못해서 그런지 그려지지가 않더라구요.

dp테이블 그리면서 생각을 추적하는 방법을 곁들여서 설명을 또 한번 부탁드려도 될지요?

Q2-1. dp 인덱싱 부분을 제 입맛대로 조금 조작을 해봤는데요. 무슨 이유 때문에 아래의 코드는 90%에서 오류가 나는지 분석이 어렵습니다. 제가 첨부한 코드를 예시로 사용해서 설명을 Q2.에 대한 설명을 비교해주시면 감사드리겠습니다!

# 바텀업DP 풀이

# 물건의 수, 배낭의 무게
# 4, 7
N, B = map(int, input().split())

# col_idx: 0, 1
# row_idx: 0, 1~3
# [idx][0]: Weight, [idx][1]: Value
items = [list(map(int, input().split())) for _ in range(N)]

# bag_wigth(col_idx): 0, 1~7
# item_idx(row_idx): 0, 1~3
dp = [[0 for _ in range(B+1)] for _ in range(N)]


# idx: 0~3
# bag_weight: 0~7
for idx in range(N):
    item_weight = items[idx][0]
    item_value = items[idx][1]
    for bag_weight in range(B+1):
        if item_weight > bag_weight:
            dp[idx][bag_weight] = dp[idx-1][bag_weight]
        else:
            dp[idx][bag_weight] = max(
                dp[idx-1][bag_weight - item_weight] + item_value,
                dp[idx-1][bag_weight])

print(items)
print(dp)
print(dp[N-1][B])

늘 친절한 답변에 감사드리며..!

저도 더욱 발전해서 코딩센세처럼 지식을 나누는 기쁨을 누릴수있도록 노력하겠습니다!

 p.s. 사실 솔직히 말씀드리면 print(dp[N-1][B]) 에서 N-1을 해야 하는 이유도 완벽하게 이해하지 못햇슴당 ㅎㅎ..