상태와 전이 정의하기
dp[i]가 의미하는 바를 정확히 정의합니다
상태와 전이 정의하기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
동적 계획법의 핵심
모든 동적 계획법은 먼저 상태를 정의하는 것에서 시작합니다. dp[i]는 실제로 무엇을 나타내나요? 이 문장을 정확하게 정하면 나머지는 자연스럽게 따라옵니다.
상태는 정확해야 합니다
의미를 말로 써 보세요. dp[i] = 처음 i개 항목에 대한 답. 모호한 상태 정의는 잘못된 점화식으로 이어집니다.
dp[i] = best total using items 0..i-1전이
전이는 dp[i]가 이전 상태들로부터 어떻게 만들어지는지 알려 줍니다. 풀이의 핵심에 있는 점화식입니다.
dp[i] = dp[i-1] + dp[i-2]기본 상태가 기준을 잡습니다
기본 상태는 직접 알고 있는 가장 작은 상태입니다. 올바른 기준이 없으면 그 이후의 모든 값이 잘못된 방향으로 어긋납니다.
dp[0] = 1계산 순서 선택하기
각 상태는 자신이 의존하는 상태를 계산한 후에 채워야 합니다. 이 의존 관계가 반복문의 방향을 결정합니다.
for i in range(1, n+1): ...답은 어디에 있나요
최종 결과가 들어 있는 칸을 정해야 합니다. 보통은 dp[n]이지만, 때로는 전체 표에서 최댓값을 구해야 합니다.
answer = dp[n] # or max(dp)상태 개수 세기
서로 다른 상태의 수가 시간 예산을 결정합니다. n개 항목에 대한 1차원 dp는 채워야 할 상태가 O(n)개입니다.
전이 하나의 비용
전체 시간은 상태 수에 전이 하나를 처리하는 작업량을 곱한 값입니다. n개의 상태에서 O(n) 전이를 수행하면 O(n²)이 됩니다.
필요할 때 차원 추가하기
인덱스 하나로 상황을 표현할 수 없다면 인덱스를 하나 더 추가합니다. 두 번째 차원을 추가하면 dp[i]가 dp[i][j]가 됩니다.
dp = [[0]*(c+1) for _ in range(n+1)]선택 복원
실제 해를 복원하려면 각 상태에서 어떤 전이가 최선이었는지 저장한 다음, 정답에서부터 거꾸로 따라가면 됩니다.
choice[i] = "take"재사용 가능한 점검표
상태, 전이, 기저 사례, 순서, 정답입니다. 이 다섯 가지를 확실히 정하면 거의 모든 DP 점화식이 자연스럽게 정리됩니다.
빠른 확인
DP를 설계하고 있습니다. dp[i]는 무엇을 나타냅니까?
복습: 이름을 정한 뒤 해결하기
이제 상태를 정의하고, 전이를 작성하고, 기저 사례를 설정하고, 정답을 찾을 수 있습니다. 이 설계도 덕분에 DP는 추측이 아니라 정해진 절차가 됩니다.
자주 묻는 질문
“상태와 전이 정의하기” 강의는 무료인가요?
네 — “상태와 전이 정의하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“상태와 전이 정의하기”에서 뭘 배우나요?
dp[i]가 의미하는 바를 정확히 정의합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“상태와 전이 정의하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 메모이제이션과 타뷸레이션 비교
- 상태와 전이 정의하기
- 계단 오르기와 동전 조합
- 최장 증가 부분 수열