인프런 커뮤니티 질문&답변
작성한 질문수
11726 런타임 질문
해결된 질문
24.10.12 18:03 작성
·
43
0
안녕하세요 강사님,
백준 11726번 관련 질문 드립니다.
노션에 나온 정답지는
# input
N = int(input())
# solve
dp = [0] * (N + 2)
dp[1] = 1
dp[2] = 2
for n in range(3, N + 1):
dp[n] = (dp[n-1] + dp[n-2]) % 10007
print(dp[N])
으로 되어있습니다.
그런데 강의에서는 dp = [0] * (N + 2)부분이 dp = [0] * (N + 1)로 되어있습니다.
백준에 dp = [0] * (N + 1)로 제출하면 런타임 에러가 발생하는데,
그 이유를 알 수 있을까요?
dp[N]까지 접근하는건데, 0번째 인덱스를 고려한 N+1이아닌, N+2는 왜 필요한지 모르겠습니다.
(강의나 노션에 추가 설명이 보이지 않아서 여쭤봅니다)
감사합니다.
답변 2
0
2024. 10. 13. 19:40
안녕하세요. 타이거님!
N에 상관없이 기본적으로 dp[0]과 dp[1]을 초기값 처리할 때 접근하기 때문입니다.
dp 배열의 크기를 N + 1로 한다면 N = 0일 때, dp[1]에 접근하지 못하기 때문에 런타임 에러가 나게 됩니다.
즉, N = 0일 때도 dp[1]까지 접근할 수 있게 하기 위해서 dp 배열의 크기를 N + 2로 했다고 생각하시면 됩니다.
비슷한 상황에 대한 설명이 섹션2의 '재귀함수 이해하기 [문제풀이] : BOJ 10870' 강의의 4:34 - 5:02 부분에 설명이 나와 있으니 참고하면 될 것 같습니다.
추가로 해당 부분에 대한 설명을 강의 자료에 추가해 놓겠습니다.
또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.
감사합니다. :)
0
2024. 10. 12. 18:06
안녕하세요, 인프런 AI 인턴입니다.
타이거님께서 질문하신 백준 11726번 문제의 런타임 에러에 대한 원인은 DP 배열의 길이가 문제의 요구사항을 충족하지 못하기 때문이라고 예상됩니다. 백준 문제에서는 피보나치 수열과 유사한 DP 문제의 특성상, N이 1 또는 2일 경우에도 문제 없도록 미리 초기화가 필요합니다.
기본적으로 dp = [0] * (N + 2)는 인덱스 에러를 방지하기 위한 안전 조치로, N이 작을 때도 배열 인덱스 접근 시 문제가 없도록 설계된 것입니다.
dp = [0] * (N + 1)로 설정하면, 예를 들어 N이 2일 때dp[2]까지는 맞지만, 만약 루프에서dp[n-1]과dp[n-2]까지의 접근이 필요한 경우, 인덱스를 초과하게 되는 경우가 발생할 수 있습니다. 따라서dp = [0] * (N + 2)로 배열을 선언하여dp[n-2]까지의 계산에 대비하는 편이 안전한 방법입니다.
추가적으로 이러한 문제들은 각 언어의 인덱싱 특성과 문제에서 요구하는 초기값 설정의 이해가 필요합니다. 백준 문제에서는 다양한 언어로 실험하며 초기 설정을 기반으로 런타임 에러를 해결하는 것이 중요합니다.
질문자님의 이해를 돕고자 관련 내용을 참고할 수 있는 기존 답변 링크를 추천드립니다:
- 백준 DP 문제와 인덱스 에러 해결 게시글을 참조하여 배열 초기화에 대한 다양한 방법과 각 경우의 수에 대한 상세 설명을 확인해 보세요.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
2024. 10. 15. 16:40
강사님 우선 답변 감사합니다!
추가 질문이 있습니다.
문제에서는 (1 ≤ n ≤ 1,000) 으로 n이 1부터 시작으로 되어있는데,
이 부분이랑 다른 이야기인가요?