계단 오르기와 동전 조합
기초부터 고전적인 1차원 점화식을 익힙니다
계단 오르기와 동전 조합은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
계단 오르기 문제 만나기
한 번에 1칸 또는 2칸 오를 수 있습니다. n번째 계단에 도달하는 방법은 몇 가지입니까? 이 고전적인 1차원 DP는 사실 피보나치 수열입니다.
점화식 찾기
i번째 계단에 서려면 i-1 또는 i-2에서 와야 합니다. 따라서 dp[i] = dp[i-1] + dp[i-2]가 되며, 마지막 두 이동을 모두 더합니다.
dp[i] = dp[i-1] + dp[i-2]기저 사례 설정
바닥에 머무는 방법은 하나이고, 1번째 계단에 도달하는 방법도 하나입니다. 이 기저 사례들이 전체 표의 출발점이 됩니다.
dp[0], dp[1] = 1, 1표를 채우고 정답 읽기
위쪽으로 반복하면 마지막 칸에 개수가 저장됩니다. 전체 해법은 아주 작은 표 채우기 반복문입니다.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]변수 두 개로 줄이기
마지막 두 값만 필요하므로 배열을 없앨 수 있습니다. 이 O(1) 공간 버전은 경연에서 특히 자주 사용됩니다.
a, b = 1, 1
for _ in range(n):
a, b = b, a+b동전 조합으로 전환
동전의 액면가가 주어졌을 때 금액 A를 만드는 방법의 수를 구합니다. 여기서는 순서가 중요하지 않으므로 수열이 아니라 조합을 셉니다.
coins = [1, 2, 5]조합 표
dp[x]를 x를 만드는 방법의 수라고 합시다. 0을 만드는 방법은 하나, 즉 동전의 공집합뿐이라고 하면서 시작합니다.
dp = [0]*(A+1)
dp[0] = 1동전 반복문을 바깥에 두기
동전 반복문을 바깥에 금액 반복문을 안쪽에 둡니다. 이렇게 하면 각 조합을 정확히 한 번씩 세며 순열은 세지 않습니다.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]조합과 순열 비교
반복문의 순서를 바꾸면 대신 순서가 있는 방법을 세게 됩니다. 반복문의 중첩 순서만으로도 정답의 의미가 바뀝니다.
동전 거스름돈 최솟값 변형
동전 수를 최소화하려면 합이 아니라 최솟값을 저장합니다. 무한대로 초기화하고, 최선의 부분 문제에 1을 더합니다.
dp[x] = min(dp[x], dp[x-c] + 1)하나의 패턴, 여러 모습
계단 문제와 동전 문제는 같은 형태를 공유합니다. 각 상태가 몇 개의 이전 상태를 더하거나 그중 최솟값을 구합니다. 이 형태를 알아보면 코드는 저절로 완성됩니다.
빠른 확인
동전 조합을 셀 때 중복을 피하려면 반복문의 순서를 어떻게 해야 합니까?
복습: 마지막 이동을 더하기
이제 1차원 점화식으로 계단 문제와 동전 개수 세기를 해결할 수 있습니다. 각 정답은 이전 상태 몇 개를 더한 값이며, 반복문 순서가 조합과 순열을 결정합니다.
자주 묻는 질문
“계단 오르기와 동전 조합” 강의는 무료인가요?
네 — “계단 오르기와 동전 조합” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“계단 오르기와 동전 조합”에서 뭘 배우나요?
기초부터 고전적인 1차원 점화식을 익힙니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“계단 오르기와 동전 조합” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 메모이제이션과 타뷸레이션 비교
- 상태와 전이 정의하기
- 계단 오르기와 동전 조합
- 최장 증가 부분 수열