학습 본문으로 건너뛰기
VAIRODE
동적 계획법 상태 연구소43번째 작은 수업
오늘은 질문 하나만 해결해요43 / 72

처음이어도 괜찮아요 · 그림부터 시작해요

각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요

오늘은 이것 하나만

“각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요”에서 무엇을 먼저 알아야 할까요?

먼저 떠올릴 생활 장면숫자 블록을 상자에 한 번씩만 넣어 정확한 무게 표시를 맞추는 것과 같아요.
  1. 1짧은 이야기 읽기
  2. 2내 생각 하나 고르기
  3. 3네 걸음 같이 보기
  4. 4내 말로 한 줄 적기
오늘의 작은 이야기
먼저 이 장면만 천천히 읽어요

“각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요” 그림에서 무엇이 먼저 달라질지 골라 볼까요?

정답을 몰라도 괜찮아요. 지금 생각과 가장 가까운 것을 골라요.

02 · 낯선 말부터 풀기

정확한 이름보다 먼저 쉬운 뜻을 읽어요

처음 보는 말도 책 읽듯 풀어봐요

이 수업은 쉬운 뜻과 생활 예를 아직 함께 준비하지 못했어요. 설명 없는 정확한 이름은 먼저 보여 주지 않을게요.

그림에서 찾을 쉬운 규칙

  1. 01그림 살펴보기: “각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요”에서 달라지는 사람·칸·횟수 중 하나를 찾아요.
  2. 02작은 질문 만들기: 지금 장면에서 알아야 할 답을 내 말로 한 문장만 말해요.
  3. 03순서대로 이어 보기: 바로 답할 수 있는 가장 작은 장면에서 다음 장면으로 가요.
  4. 04다시 확인하기: 마지막 답이 만들어진 길을 되짚고, 다른 작은 예에서도 같은지 봐요.

03 · 그림으로 보기

각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요 · 점수판 SVG

각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요를 보고, 따라 하고, 다시 해보는 그림생활 질문부터 상태 문장, 점화식 화살표, 독립 검산까지 순서로 보여 주는 정적 SVG: 각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요01오늘의 장면dp43 · 숫자 블록을 상자에 한번씩만 넣어 정확한 무게 표시를맞추는 것과 같아요.02첫 걸음그림 살펴보기: “각 숫자를 한번씩 써서 목표를 만들 수 있는지봐요”에서 달라지는 사람·칸·횟수…03결과 열기내 답을 먼저 적은 뒤 결과를 열어봐요.직접 살펴보는 그림 · 부분집합 합의 가능 여부의 질문·예측·state·dependency·검산 순서를 한눈에 보여 준다.처음 생각과 달라도 괜찮아요. 달라진 첫 단계만 다시 봐요.
  1. 01오늘의 장면dp43 · 숫자 블록을 상자에 한 번씩만 넣어 정확한 무게 표시를 맞추는 것과 같아요.
  2. 02첫 걸음그림 살펴보기: “각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요”에서 달라지는 사람·칸·횟수 중 하나를 찾아요.
  3. 03결과 열기내 답을 먼저 적은 뒤 결과를 열어 봐요.
부분집합 합의 가능 여부의 질문·예측·state·dependency·검산 순서를 한눈에 보여 준다.내 생각을 먼저 남기면 결과와 쉬운 설명을 차례로 열 수 있어요.현재 화면: 그림 요약 · 그림을 보는 방법: 정적 SVG의 질문→생활예시→예측→관찰→상태→점화식→검산 순서를 문서 흐름대로 읽는다. · 움직임 없이 보기: 자동 이동이나 전환 없이 같은 state node·dependency arrow·검산 receipt를 정적 SVG와 텍스트로 유지한다.

04 · 책처럼 천천히 되짚기

방금 한 일을 한 줄씩 다시 읽어요

dp43 · 숫자 블록을 상자에 한 번씩만 넣어 정확한 무게 표시를 맞추는 것과 같아요.

이 장면에서 주어진 것tiny-subset-sum-reachability fixture with empty·tie·state-collision·boundary
내 말로 8자 이상 적어요 · 0 / 240

05 · 이제 내가 해볼 차례

여기까지 오면 이런 일을 할 수 있어요

“각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요”에서 무엇을 먼저 알아야 할까요?

  • 그림 살펴보기: “각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요”에서 달라지는 사람·칸·횟수 중 하나를 찾아요.
  • 작은 질문 만들기: 지금 장면에서 알아야 할 답을 내 말로 한 문장만 말해요.
  • 순서대로 이어 보기: 바로 답할 수 있는 가장 작은 장면에서 다음 장면으로 가요.
  • 다시 확인하기: 마지막 답이 만들어진 길을 되짚고, 다른 작은 예에서도 같은지 봐요.
오늘 해낼 일과 다 했다고 볼 기준 보기쉬운 순서를 익힌 뒤 더 정확히 확인하고 싶을 때 열어요.

코드 전에 다음 계약을 적는다: reachable[s]는 지금까지 본 숫자를 각각 한 번 이하 사용해 합 s를 만들 수 있음을 뜻한다. reachable[0]=true에서 각 양수 값을 capacity 역방향으로 훑어 reachable[s]∨=reachable[s-value] 한다. 이어서 다음 위험을 collision witness·귀납·독립 oracle·mutant·비용 receipt 중 맞는 증거로 확인한다: 방법 수와 가능 여부를 섞거나 정방향 update로 같은 숫자를 반복 사용한다.

  • dp43의 state가 답하는 질문과 모든 index 의미를 생활 말로 설명한다.
  • dp43의 recurrence 경우·base·dependency order를 빠짐없이 적는다.
  • dp43의 실제 답을 복원하고 correctness와 state×transition 비용을 분리한다.
  • dp43 AI 후보와 expected oracle이 recurrence·cache·tie helper를 공유하지 않게 한다.

06 · 자주 헷갈리는 지점

틀린 답도 이유를 알면 다음에는 맞힐 수 있어요

처음부터 모두 맞힐 필요는 없어요.괜찮아요. 마지막 숫자는 잠시 가리고 “각 숫자를 한 번씩 써서 목표를 만들 수 있는지 봐요” 그림에서 먼저 달라지는 한 곳만 다시 찾아봐요.

헷갈리기 쉬운 이유 세 가지 보기내가 어디에서 다르게 생각했는지 찾고 싶을 때 열어요.
01dp43에서 같은 숫자가 나오면 같은 state다.

한 번 더 생각해 볼 질문같은 숫자지만 다음 합법 선택이 다른 두 이력을 만들 수 있는가?

이렇게 고쳐 생각해요state는 저장된 숫자가 아니라 앞으로 답할 부분 문제와 필요한 정보의 계약이다.

02dp43 점화식을 적었으므로 모든 입력에서 맞다.

한 번 더 생각해 볼 질문빠진 마지막 선택·겹친 경우·도달 불가 base 중 어느 반례가 있는가?

이렇게 고쳐 생각해요경우가 완전하고 배타적인지, base가 참인지, 더 작은 상태의 정확성이 원래 답으로 이어지는지 증명해야 한다.

03dp43 표가 자연스럽게 채워지므로 상태와 비용이 증명됐다.

한 번 더 생각해 볼 질문같은 animation을 보이면서 틀린 loop order나 불충분 state를 가진 mutant를 만들 수 있는가?

이렇게 고쳐 생각해요animation은 관찰 도구이며 독립 oracle·proof·state 수·transition work receipt를 대신하지 않는다.

07 · 더 궁금할 때만 보기

선생님과 검토자를 위한 믿을 만한 원문

원문과 어디까지 참고했는지 펼쳐 보기처음 배우는 동안에는 열지 않아도 괜찮아요.
ACM Press · IEEE Computer Society Press · AAAI Press · 공개 문서를 확인했어요ACM Press · IEEE Computer Society Press · AAAI Press의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.

International Olympiad in Informatics · 공개 문서를 확인했어요International Olympiad in Informatics의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.

National Institute of Standards and Technology · 공개 문서를 확인했어요National Institute of Standards and Technology의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.

ISO/IEC JTC 1/SC 22/WG21 · 공개 문서를 확인했어요ISO/IEC JTC 1/SC 22/WG21의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.

Massachusetts Institute of Technology OpenCourseWare · 2026년 7월 28일에 확인했어요Massachusetts Institute of Technology OpenCourseWare의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.

Stanford University CS161 · 2026년 7월 28일에 확인했어요Stanford University CS161의 공식 원문 보기

이 수업의 설명이 공식 규칙과 맞는지 선생님과 검토자가 다시 확인할 때 쓰는 원문이에요.