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

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

한 번 고른 답이 끝까지 괜찮은지 확인해요

오늘은 이것 하나만

오늘은 “한 번 고른 답이 끝까지 괜찮은지 확인해요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

먼저 떠올릴 생활 장면친구와 카드 답을 하나씩 비교하며 처음 달라진 곳에 표시를 붙이는 상황과 같아요.
  1. 1짧은 이야기 읽기
  2. 2내 생각 하나 고르기
  3. 3네 걸음 같이 보기
  4. 4내 말로 한 줄 적기
오늘의 작은 이야기
먼저 이 장면만 천천히 읽어요

“한 번 고른 답이 끝까지 괜찮은지 확인해요” 장면을 보고, 오늘의 규칙에 맞는 첫 카드를 예상해 보세요.

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

02 · 낯선 말부터 풀기

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

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

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

그림에서 찾을 쉬운 규칙

  1. 01친구와 카드 답을 하나씩 비교하며 처음 달라진 곳에 표시를 붙이는 상황과 같아요.
  2. 02먼저 “한 번 고른 답이 끝까지 괜찮은지 확인해요” 규칙을 말해요.
  3. 03첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  4. 04왜 그 카드를 골랐는지 한 문장으로 말해요.

03 · 그림으로 보기

한 번 고른 답이 끝까지 괜찮은지 확인해요 · 선택 비교 그림

체험 학습 · 한 번에 한 칸

지금 고른 답을 끝까지 믿어도 될까요?

64가지 조합 · 512개 확인 칸

탐욕법은 눈앞에서 가장 좋아 보이는 하나를 먼저 고르는 방법이에요. 답을 외우는 대신 작은 선택을 직접 하고, 따로 계산한 답과 비교해 “언제 믿고 언제 멈춰야 하는지” 찾아봐요.

선생님용 정확한 실험 범위 보기

선택 결과가 아니라 한 번의 선택이 안전해지는 objective·feasibility·local rule·증명 또는 반례를 64선택·512프레임에서 판정한다.

  1. 01오늘 할 일
  2. 02생활 질문
  3. 03먼저 예상
  4. 04한 칸 따라가기
  5. 05왜 맞는지
  6. 06작은 문제
  7. 07바로 피드백
  8. 08다른 문제
오늘은 이것 하나만 기억해요“지금 좋아 보인다”는 느낌만으로는 부족해요. 남은 답을 망치지 않는 이유까지 보여야 탐욕법을 쓸 수 있어요.

처음부터 증명을 알 필요는 없어요. 아래에서 문제와 규칙을 고른 뒤 첫 후보 하나만 예상해 보세요.

1. 어떤 생활 문제로 시작할까요?
2. 무엇을 먼저 고르는 규칙으로 해볼까요?
3. 얼마나 크고 까다로운 예로 시험할까요?
문제겹치지 않는 활동을 가장 많이 고르기

먼저 끝나는 활동을 고르면 남은 시간에 더 많은 활동을 넣을 수 있을까요?

꼭 지킬 약속 · 선택한 활동끼리 시간이 겹치지 않아야 해요.
첫 선택 규칙가장 먼저 끝나는 후보부터

가장 먼저 끝나는 후보를 고르고, 같으면 후보 글자가 앞선 것을 골라요.

동점일 때 · 후보 번호가 앞선 것을 먼저 골라요
시험 크기후보 8개 · 손으로 따라가기

전체 후보 8개 · 이번 화면 대표 5개

작은 예에서 내 선택과 따로 계산한 답을 한 칸씩 비교해요.

STEP 1 · 직접 확인

무엇을 좋게 만들고 어떤 약속을 지킬지 정하기

가장 크게 만들지 작게 만들지, 무엇을 고를 수 없는지 먼저 정했나요?
문제에서 가장 좋게 만들 것과 꼭 지켜야 할 약속을 먼저 찾아요.

후보 8개 · 손으로 따라가기에서 “겹치지 않는 활동을 가장 많이 고르기”의 목표와 가능한 선택 조건을 잠갔습니다.

전체 후보 8개 가운데 이번 화면에서는 대표 5개만 크게 보여줘요. 큰 문제도 같은 규칙으로 확인한 숫자는 아래 영수증에서 볼 수 있어요.

선택 규칙과 독립 검산 답의 첫 차이후보만 공개되어 있고 선택 규칙의 답과 독립 검산 답은 아직 가려져 있습니다.CHOICE LEDGER · 눈으로 먼저 비교하기같은 후보에서 두 답이 어디까지 나란히 가는지 확인해요.후보A01B02C03D04E05선택 규칙먼저 무엇을 고를지 예상하면 이 줄이 열립니다.검산 답독립 검산 답은 예측 뒤에 공개합니다.결과를 보기 전에 선택 규칙이 고를 첫 후보를 말해 보세요.
AA · [0, 1)

시작 0 · 끝 1

아직 보지 않음
BB · [0, 3)

시작 0 · 끝 3

아직 보지 않음
CC · [1, 3)

시작 1 · 끝 3

아직 보지 않음
DD · [3, 5)

시작 3 · 끝 5

아직 보지 않음
EE · [5, 7)

시작 5 · 끝 7

아직 보지 않음

왜 이 선택을 믿을까요?

왜 맞는지, 어디서 틀리는지

필요한 칸만 확인
증명 단계에서 열려요

한 장 바꾸어도 손해가 없나요?

먼저 어떤 후보를 고를지 예상하세요. 근거와 검산 답은 뒤에서 한 칸씩 엽니다.

증명 단계에서 열려요

매 순간 뒤처지지 않나요?

먼저 어떤 후보를 고를지 예상하세요. 근거와 검산 답은 뒤에서 한 칸씩 엽니다.

증명 단계에서 열려요

두 무리를 잇는 안전한 선인가요?

먼저 어떤 후보를 고를지 예상하세요. 근거와 검산 답은 뒤에서 한 칸씩 엽니다.

증명 단계에서 열려요

규칙을 깨는 작은 예가 있나요?

먼저 어떤 후보를 고를지 예상하세요. 근거와 검산 답은 뒤에서 한 칸씩 엽니다.

숫자로 다시 확인하기

답과 숫자 영수증

같은 입력이면 늘 같은 결과가 나오는 연습 모형
숫자 영수증은 마지막 작은 칸에서 열려요.

먼저 후보를 고르고 두 답을 비교하세요. 큰 숫자가 앞서 보이면 생각보다 선택 이유를 놓치기 쉬워요.

1 / 8첫 선택을 직접 골라보기

한 번에 한 칸만 엽니다. 이미 연 단계는 위 버튼으로 다시 볼 수 있어요.

아직 확인하는 중

마지막 판정은 아직 잠겨 있어요

확인 전
정답을 먼저 보여주지 않아요.

네 단계를 끝까지 눌러야 마지막 판정이 열립니다. 그 전에 내가 고른 이유를 한 문장으로 말해 보세요.

교재 이름은 “한 번 고른 답이 끝까지 괜찮은지 확인해요”입니다. 이 연습은 64가지 선택을 같은 방법으로 비교하며, 모두 512칸으로 이루어져 있어요. 실제 프로그램이 걸리는 시간은 따로 재야 하고, 한 예에서 맞았다는 이유만으로 모든 문제에 같은 규칙을 쓰면 안 돼요.

04 · 책처럼 천천히 되짚기

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

gd64 · 친구와 카드 답을 하나씩 비교하며 처음 달라진 곳에 표시를 붙이는 상황과 같아요.

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

05 · 이제 내가 해볼 차례

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

오늘은 “한 번 고른 답이 끝까지 괜찮은지 확인해요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

  • 친구와 카드 답을 하나씩 비교하며 처음 달라진 곳에 표시를 붙이는 상황과 같아요.
  • 먼저 “한 번 고른 답이 끝까지 괜찮은지 확인해요” 규칙을 말해요.
  • 첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  • 왜 그 카드를 골랐는지 한 문장으로 말해요.
오늘 해낼 일과 다 했다고 볼 기준 보기쉬운 순서를 익힌 뒤 더 정확히 확인하고 싶을 때 열어요.

4 workload×4 policy×4 profile의 64선택과 선택당 8프레임, 총 512프레임을 objective·feasibility·local choice·proof/counterexample·verdict로 판정한다.를 실행 전 봉인하고 애니메이션·최종 숫자·AI 설명 하나를 independent proof로 사용한다.을 반례·불변식·exchange·stays-ahead·cut 또는 independent oracle로 판정한다.

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

06 · 자주 헷갈리는 지점

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

처음부터 모두 맞힐 필요는 없어요.지금은 몰라도 괜찮아요. “한 번 고른 답이 끝까지 괜찮은지 확인해요” 규칙과 고른 뒤 남는 카드만 다시 살펴봐요.

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

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

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

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

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

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

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

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

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