인프런 커뮤니티 질문&답변
작성한 질문수
DP 알고리즘 index 0 이유?
작성
·
19
0
💡 질문 작성 가이드
보다 빠르고 정확한 답변을 위해, 아래 사항을 참고해 질문을 작성해주세요.
1. 간단한 내용은 ChatGPT로 먼저 확인해보세요.
기본 개념이나 용어 설명은 ChatGPT를 활용하는 것이 더 빠르고 효율적일 수 있습니다.
2. 질문하실 때, 아래 내용을 함께 적어주시면 좋아요.
어느 파트인지
풀이 코드 > Bottom-Up 방식의 구현내가 이해한 내용 + 궁금한점
cost = [[0, 0, 0]]
dp = [[-1, -1, -1] for _ in range(N + 1)]
해당 부분을 제거 하고
cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1, -1, -1] for _ in range(N)]초기값 처리에서도 1번째가 아닌 0번째 초기화 처리
for문에서도 range(2, n+1)이 아닌 range(1, n) 처리
이렇게 0번째 배열부터 사용하도록 해도 같은 결과를 추출 할 수 있는데
굳이 0번째 배열을 [0,0,0], [-1,-1,-1]로 저장해놓는 이유가 있는지 궁금합니다.
0번째 배열을 쓰는 문제가 있는건지,,, 놓친 부분이 있는건지,, 해서 여쭤봅니다.
N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1, -1, -1] for _ in range(n)]
dp[0][0] = costs[0][0]
dp[0][1] = costs[0][1]
dp[0][2] = costs[0][2]
# DP Table 갱신
for i in range(1, n): # dp[i][0 ~ 2]
# dp[i][0]
dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2])
# dp[i][1]
dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2])
# dp[i][2]
dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1])답변 2
0
안녕하세요, 김가람님!
DP Table을 만들 때 보통 0-index 방식 또는 1-index 방식을 사용합니다.
0-index 방식: 인덱스를 0부터 사용하는 방식
1-index 방식: 인덱스를 1부터 사용하는 방식
문제 설명에서 보통 '첫 번째 집', '1번부터' 처럼 1부터 시작하는 경우가 많아, 저 같은 경우에 DP Table을 만들 때 기본적으로 1-index 방식을 사용하는 걸 선호합니다.
인덱스 0인 부분을 사용하지 않는 경우에도, 문제 설명과의 일치를 중요하게 생각하여 1-index를 사용하는 편입니다. (이번 문제 포함)
아마 DP 관련 강의를 이어서 수강하다 보면, DP Table을 만들 때 (0-index보다) 1-index를 기본으로 하는 게 직관적이라는 것을 느끼실 수 있을 겁니다!
문제에서 설명하는 번호와 일치하게 코드 작성 가능 (즉, dp[i]는 i번째 집과 관련된 정보를 의미)
초기값 처리를 하지 않을 경우에, 인덱스 0인 부분에 특정 값을 넣어 둬야 함.
(아래 이미지는 BOJ 1149 자료의 관련 설명 부분을 캡처한 사진입니다)
결론적으로, 이번 문제만 봤을 때 질문자님이 말씀하신 대로 0-index 기반으로 사용하여 풀어도 무방합니다. 이후에 강의를 들어도 0-index가 편하시다면 그렇게 코드 스타일을 잡아도 무방합니다!
질문에 대해 만족스러운 답변이 되었기를 바랍니다!
추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄
0
안녕하세요, 인프런 AI 인턴입니다.
김가람님께서 작성해 주신 질문은 다이나믹 프로그래밍(DP) 알고리즘 구현 중에 초기화 부분에서 0번째 인덱스의 필요성에 대한 것입니다. 이를 좀 더 명확히 이해하기 위해 간단히 설명드리겠습니다.
DP에서 0번째 인덱스를 사용하는 경우는 일반적으로 초기화를 보다 명료하게 처리하기 위함입니다. 0번째 배열이 주로 [0, 0, 0]이나 [-1, -1, -1]로 설정되는 이유는 다음과 같습니다:
초기 조건 명확화: 특정 문제에서는 DP의 첫 번째 단계 초기화로서, 0번째 인덱스를 사용하여 기본 상태를 설정하는 것이 유리합니다. 이는 초기 값이 반드시 1부터 시작하지 않도록 하여 문제를 유연하게 해결할 수 있게 합니다.
범위 체크의 용이성: 0부터 시작할 때 인덱스 범위 검사가 덜 복잡하게 됩니다. 첫 iteration을 통해 첫번째 값인 dp[0]을 직접 설정하는 경우, 이후의 logic이 보다 투명하게 이해될 수 있습니다.
식의 일관성 유지: 문제에 따라 이전 단계의 결과를 참조할 때 0번 인덱스가 필요하게 되는 경우가 많습니다. 0번 인덱스를 기시한다면 일정식의 일관성을 유지할 수 있습니다.
질문자님께서 제안하신 것처럼 꼭 0번째 인덱스를 사용하지 않고도 구현이 가능할 때도 있지만, 코드를 비교적 읽기 쉽게 유지하고 오류를 줄이기 위해 관용적으로 이용됩니다.
아래 게시물을 참고하시면 인덱스 시작점 문제에 대한 다양한 케이스를 확인할 수 있습니다:
- DP 문제의 초기화와 인덱스 설정의 중요성 게시물에서 DP 문제에 대한 더 많은 설명과 예를 확인하실 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.