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

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

답에 꼭 필요한 기억만 골라 엮어 봐요

오늘은 이것 하나만

두 상황을 같은 답 칸에 넣어도 앞으로 할 수 있는 일이 같을까요?

먼저 떠올릴 생활 장면서로 다른 색실이 같은 무늬를 만들 때만 한 매듭으로 합치고, 다른 무늬라면 새 매듭을 만드는 베틀과 같아요.
  1. 1짧은 이야기 읽기
  2. 2내 생각 하나 고르기
  3. 3네 걸음 같이 보기
  4. 4내 말로 한 줄 적기
오늘의 작은 이야기
먼저 이 장면만 천천히 읽어요

답 칸 두 개를 하나로 합치기 전에 무엇을 먼저 비교해야 할까요?

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

02 · 낯선 말부터 풀기

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

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

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

그림에서 찾을 쉬운 규칙

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

03 · 그림으로 보기

답에 꼭 필요한 기억만 골라 엮어 봐요 · 64선택 State Loom

1번째 칸, 상태의 뜻 찾기. 두 문자열의 최소 편집 횟수: 삽입·삭제·바꾸기를 사용해 한 단어를 다른 단어로 만드는 최소 횟수는 몇 번일까요?

체험 학습 · 동적 계획법

큰 문제를, 뜻이 분명한 작은 답으로 엮어 봐요.

64가지 실험 · 512개 확인 프레임

동적 계획법은 표를 외우는 기술이 아니에요. “이 칸이 무슨 질문의 답인가?”를 먼저 정하고, 작은 답이 준비되는 순서대로 한 번씩 이어 최종 답을 만드는 방법이에요.

수업의 정확한 실험 범위 보기

답에 꼭 필요한 기억만 골라 엮어 봐요답이 아니라 같은 state key에 합치는 두 이력의 미래가 같은지 먼저 보고, state·base·recurrence·dependency·복원·proof·cost·독립 oracle을 64선택·512 addressable frame에서 판정한다.

  1. 01상태 뜻
  2. 02합칠지 예상
  3. 03기저값
  4. 04점화식
  5. 05의존 순서
  6. 06표 채우기
  7. 07답 복원
  8. 08최종 감사

하나만 고르면 바로 시작해요

어떤 문제를 작은 답으로 나눠 볼까요?

연습할 문제 종류
설계와 시험 조건 바꾸기미래를 바꾸는 좌표만 저장해요 · 상태 8 경계
상태를 어떻게 기억할까요?
어떤 경계에서 확인할까요?

문제 02 · 글자 바꾸기 · 1/8

이 답 칸 하나가 무엇을 기억해야 할까요?

상태의 뜻 찾기

전체 문제를 한꺼번에 풀지 말고, 앞으로의 답을 바꾸는 좌표부터 찾아요.

작은 동적 계획법 상태 지도. 4행 4열, 0개 의존선.
상태뜻값현재 상태먼저 필요한 칸계산 순서
d[0][0]왼쪽 0글자를 오른쪽 0글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[0][1]왼쪽 0글자를 오른쪽 1글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[0][2]왼쪽 0글자를 오른쪽 2글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[0][3]왼쪽 0글자를 오른쪽 3글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[1][0]왼쪽 1글자를 오른쪽 0글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[1][1]왼쪽 1글자를 오른쪽 1글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[1][2]왼쪽 1글자를 오른쪽 2글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[1][3]왼쪽 1글자를 오른쪽 3글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[2][0]왼쪽 2글자를 오른쪽 0글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[2][1]왼쪽 2글자를 오른쪽 1글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[2][2]왼쪽 2글자를 오른쪽 2글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[2][3]왼쪽 2글자를 오른쪽 3글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[3][0]왼쪽 3글자를 오른쪽 0글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[3][1]왼쪽 3글자를 오른쪽 1글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[3][2]왼쪽 3글자를 오른쪽 2글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림
d[3][3]왼쪽 3글자를 오른쪽 3글자로 바꾸는 최소 횟수아직 가림아직 가림없음아직 가림

작은 화면에서는 지도를 좌우로 움직여 크게 볼 수 있어요.

  • 시작값
  • 먼저 읽음
  • 지금 계산
  • 계산 완료
  • 답의 경로
  • 고칠 곳

표를 보기 전에 문장부터

상태 칸 하나의 뜻

  • 답하는 질문d[i][j]는 왼쪽 문자열 앞 i글자를 오른쪽 문자열 앞 j글자로 만드는 최소 편집 횟수예요.
  • 오늘 확인할 후보기본 규칙으로 계산하는 후보
  • 꼭 필요한 좌표왼쪽 글자 경계 i · 오른쪽 글자 경계 j
  • 지금 저장한 좌표왼쪽 글자 경계 i · 오른쪽 글자 경계 j
  • 가장 작은 답d[i][0] = i, d[0][j] = j
  • 작은 답을 잇는 식d[i][j] = min(삭제, 삽입, 같으면 대각선·다르면 대각선+1)
최종 판정은 아직 잠겨 있어요

상태 뜻부터 검산까지 한 칸씩 확인해요.

상태 뜻부터 독립 검산까지 모두 확인한 뒤 하나의 첫 위반만 공개해요.

대표 그림은 최대 4×4만 보여 줍니다. 전체 상태 수와 작업량은 같은 입력에서 반복 가능한 추상 모형이며, 실제 기기 성능 측정은 아닙니다.

04 · 책처럼 천천히 되짚기

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

State Loom · weighted-interval-value/edit-distance/bounded-capacity-value/tree-independent-selection × minimal-sufficient/missing-history/redundant-history/cyclic-dependency × tiny-clean-8/ties-sealed-64/state-collision-counterexample/large-boundary-4096

이 장면에서 주어진 것4 problem family × 4 state design × 4 profile = 64 selection; 8 frame per selection; 512 addressable frame; 11 final-only verdict
내 말로 8자 이상 적어요 · 0 / 240

05 · 이제 내가 해볼 차례

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

두 상황을 같은 답 칸에 넣어도 앞으로 할 수 있는 일이 같을까요?

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

코드 전에 다음 계약을 적는다: 선택한 state key는 같은 key의 모든 이력이 같은 미래 선택과 답을 가져야 하며 dependency는 cycle 없이 base로 향한다. 상태·base·transition·순서를 봉인하고 5 tick trace 뒤 복원·귀납 proof·state×work 비용·독립 oracle을 마지막 frame에서만 판정한다. 이어서 다음 위험을 collision witness·귀납·독립 oracle·mutant·비용 receipt 중 맞는 증거로 확인한다: 예쁜 animation이나 마지막 숫자를 상태 충분성·점화식 정당성·비용 증명으로 오인한다.

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

06 · 자주 헷갈리는 지점

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

처음부터 모두 맞힐 필요는 없어요.괜찮아요. 마지막 숫자는 잠시 가리고 “답에 꼭 필요한 기억만 골라 엮어 봐요” 그림에서 먼저 달라지는 한 곳만 다시 찾아봐요.

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

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

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

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

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

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

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

한 번 더 생각해 볼 질문같은 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의 공식 원문 보기

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

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

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

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

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