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

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

매번 변하지 않아야 할 약속을 한 줄로 적어요

오늘은 이것 하나만

오늘은 “매번 변하지 않아야 할 약속을 한 줄로 적어요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

먼저 떠올릴 생활 장면보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.
  1. 1짧은 이야기 읽기
  2. 2내 생각 하나 고르기
  3. 3네 걸음 같이 보기
  4. 4내 말로 한 줄 적기
오늘의 작은 이야기
먼저 이 장면만 천천히 읽어요

“매번 변하지 않아야 할 약속을 한 줄로 적어요” 장면을 보고, 오늘의 규칙에 맞는 첫 카드를 예상해 보세요.

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

02 · 낯선 말부터 풀기

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

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

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

그림에서 찾을 쉬운 규칙

  1. 01보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.
  2. 02먼저 “매번 변하지 않아야 할 약속을 한 줄로 적어요” 규칙을 말해요.
  3. 03첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  4. 04왜 그 카드를 골랐는지 한 문장으로 말해요.

03 · 그림으로 보기

매번 변하지 않아야 할 약속을 한 줄로 적어요 · 물 보충하기 그림

매번 변하지 않아야 할 약속을 한 줄로 적어요를 보고, 따라 하고, 다시 해보는 그림매번 변하지 않아야 할 약속을 한 줄로 적어요을 관찰, 추론, 검증 세 단계로 설명하는 정적 SVG01오늘의 장면gd18 · 보물찾기에서 한 방을지날 때마다 이미 확인한 방은 다시볼 필요 없다는 약속과 같아요.02첫 걸음보물찾기에서 한 방을 지날 때마다이미 확인한 방은 다시 볼 필요없다는 약속과 같아요.03결과 열기내 답을 먼저 적은 뒤 결과를 열어봐요.직접 살펴보는 그림 · 선택 반복의 불변 문장 세우기의 관찰·추론·검증 순서를 한눈에 보여 준다.처음 생각과 달라도 괜찮아요. 달라진 첫 단계만 다시 봐요.
  1. 01오늘의 장면gd18 · 보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.
  2. 02첫 걸음보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.
  3. 03결과 열기내 답을 먼저 적은 뒤 결과를 열어 봐요.
선택 반복의 불변 문장 세우기의 관찰·추론·검증 순서를 한눈에 보여 준다.내 생각을 먼저 남기면 결과와 쉬운 설명을 차례로 열 수 있어요.현재 화면: 그림 요약 · 그림을 보는 방법: 정적 SVG의 세 칸을 문서 순서대로 읽고 아래 설명과 함께 확인한다. · 움직임 없이 보기: 자동 이동이나 전환 없이 같은 관찰·추론·검증 세 칸을 유지한다.

04 · 책처럼 천천히 되짚기

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

gd18 · 보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.

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

05 · 이제 내가 해볼 차례

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

오늘은 “매번 변하지 않아야 할 약속을 한 줄로 적어요”를 작은 카드로 해 보고, 고른 까닭을 한 문장으로 말해 봐요.

  • 보물찾기에서 한 방을 지날 때마다 이미 확인한 방은 다시 볼 필요 없다는 약속과 같아요.
  • 먼저 “매번 변하지 않아야 할 약속을 한 줄로 적어요” 규칙을 말해요.
  • 첫 카드를 고른 뒤에도 다음 선택이 남는지 표시해요.
  • 왜 그 카드를 골랐는지 한 문장으로 말해요.
오늘 해낼 일과 다 했다고 볼 기준 보기쉬운 순서를 익힌 뒤 더 정확히 확인하고 싶을 때 열어요.

초기화·유지·종료의 세 구간으로 greedy invariant를 서술한다.를 실행 전 봉인하고 반복 중 관찰을 invariant라고 부르지만 종료 시 objective와 연결하지 않는다.을 반례·불변식·exchange·stays-ahead·cut 또는 independent oracle로 판정한다.

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

06 · 자주 헷갈리는 지점

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

처음부터 모두 맞힐 필요는 없어요.지금은 몰라도 괜찮아요. “매번 변하지 않아야 할 약속을 한 줄로 적어요” 규칙과 고른 뒤 남는 카드만 다시 살펴봐요.

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

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

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

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

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

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

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

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

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