학습 본문으로 건너뛰기
VAIRODE
그리디 선택 연구소10번째 작은 수업
오늘은 질문 하나만 해결해요10 / 72

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

큰 동전부터 내기 전에 동전 묶음을 봐요

오늘은 이것 하나만

오늘은 “큰 동전부터 내기 전에 동전 묶음을 봐요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

먼저 떠올릴 생활 장면지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.
  1. 1짧은 이야기 읽기
  2. 2내 생각 하나 고르기
  3. 3네 걸음 같이 보기
  4. 4내 말로 한 줄 적기
오늘의 작은 이야기
먼저 이 장면만 천천히 읽어요

“큰 동전부터 내기 전에 동전 묶음을 봐요” 장면을 보고, 오늘의 규칙에 맞는 첫 카드를 예상해 보세요.

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

02 · 낯선 말부터 풀기

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

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

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

그림에서 찾을 쉬운 규칙

  1. 01지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.
  2. 02먼저 “큰 동전부터 내기 전에 동전 묶음을 봐요” 규칙을 말해요.
  3. 03첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  4. 04왜 그 카드를 골랐는지 한 문장으로 말해요.

03 · 그림으로 보기

큰 동전부터 내기 전에 동전 묶음을 봐요 · 이어달리기 그림

큰 동전부터 내기 전에 동전 묶음을 봐요를 보고, 따라 하고, 다시 해보는 그림큰 동전부터 내기 전에 동전 묶음을 봐요을 관찰, 추론, 검증 세 단계로 설명하는 정적 SVG01오늘의 장면gd10 · 지갑에 든 동전 종류가바뀌면 같은 금액도 다른 방법으로내야 하는 상황과 같아요.02첫 걸음지갑에 든 동전 종류가 바뀌면 같은금액도 다른 방법으로 내야 하는상황과 같아요.03결과 열기내 답을 먼저 적은 뒤 결과를 열어봐요.직접 살펴보는 그림 · 동전 선택 규칙의 조건 적기의 관찰·추론·검증 순서를 한눈에 보여 준다.처음 생각과 달라도 괜찮아요. 달라진 첫 단계만 다시 봐요.
  1. 01오늘의 장면gd10 · 지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.
  2. 02첫 걸음지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.
  3. 03결과 열기내 답을 먼저 적은 뒤 결과를 열어 봐요.
동전 선택 규칙의 조건 적기의 관찰·추론·검증 순서를 한눈에 보여 준다.내 생각을 먼저 남기면 결과와 쉬운 설명을 차례로 열 수 있어요.현재 화면: 그림 요약 · 그림을 보는 방법: 정적 SVG의 세 칸을 문서 순서대로 읽고 아래 설명과 함께 확인한다. · 움직임 없이 보기: 자동 이동이나 전환 없이 같은 관찰·추론·검증 세 칸을 유지한다.

04 · 책처럼 천천히 되짚기

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

gd10 · 지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.

이 장면에서 주어진 것tiny-coin-change-contract fixture with empty·tie·counterexample boundary
내 말로 8자 이상 적어요 · 0 / 240

05 · 이제 내가 해볼 차례

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

오늘은 “큰 동전부터 내기 전에 동전 묶음을 봐요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

  • 지갑에 든 동전 종류가 바뀌면 같은 금액도 다른 방법으로 내야 하는 상황과 같아요.
  • 먼저 “큰 동전부터 내기 전에 동전 묶음을 봐요” 규칙을 말해요.
  • 첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  • 왜 그 카드를 골랐는지 한 문장으로 말해요.
오늘 해낼 일과 다 했다고 볼 기준 보기쉬운 순서를 익힌 뒤 더 정확히 확인하고 싶을 때 열어요.

coin denomination·target·동전 수 제한·목표를 명시하고 policy를 검증한다.를 실행 전 봉인하고 익숙한 화폐 예제에서 성공한 규칙을 임의 동전 체계로 일반화한다.을 반례·불변식·exchange·stays-ahead·cut 또는 independent oracle로 판정한다.

  • gd10 input·feasible set·objective·tie·irrevocability를 실행 전에 기록한다.
  • gd10 선택 trace에서 첫 divergence와 남은 feasible state를 설명한다.
  • gd10 proof 또는 최소 counterexample를 candidate와 독립된 방식으로 제출한다.
  • gd10 problem theorem·algorithm proof·API contract·measurement claim을 섞지 않는다.

06 · 자주 헷갈리는 지점

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

처음부터 모두 맞힐 필요는 없어요.지금은 몰라도 괜찮아요. “큰 동전부터 내기 전에 동전 묶음을 봐요” 규칙과 고른 뒤 남는 카드만 다시 살펴봐요.

헷갈리기 쉬운 이유 세 가지 보기내가 어디에서 다르게 생각했는지 찾고 싶을 때 열어요.
01gd10에서 지금 가장 좋아 보이는 값이면 전체 최적이다.

한 번 더 생각해 볼 질문같은 첫 선택이 더 나쁜 마지막 답을 만드는 작은 입력을 만들 수 있는가?

이렇게 고쳐 생각해요local choice와 global objective를 연결하는 proof가 별도로 필요하다.

02gd10 예제 세 개가 맞았으므로 모든 입력에서 맞다.

한 번 더 생각해 볼 질문동점·빈 입력·integrality·목표 변경 중 어느 축에서 주장이 깨지는가?

이렇게 고쳐 생각해요finite examples는 관찰이며 exchange·stays-ahead·cut proof 또는 정확한 범위 제한을 대신하지 않는다.

03gd10 구현이 실행되므로 선택 정책도 증명됐다.

한 번 더 생각해 볼 질문공식 API 문서가 보장한 사실과 문제의 최적성 주장을 두 열로 나눌 수 있는가?

이렇게 고쳐 생각해요도구의 API 계약과 알고리즘 최적성 정리는 다른 claim layer다.

07 · 더 궁금할 때만 보기

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

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

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

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

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

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

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