중복 탐지 제약·비용·실측 관측소

1. 01

   찾아보기 · 기초

   cx64 recognize · 중복 탐지 제약·비용·실측 관측소: duplicate detection·constraint observatory 표식 중 “같은 중복 탐지 semantics 아래 scenario·strategy·scale을 봉인하고 exact/expected/worst cost·space·domain 전제·budget을 함께 판정한다.”을 만족하는 판정을 고른다.

   상황

   n=32의 일회성 integer 목록에서 입력을 바꾸지 않고 중복 존재 여부만 판정한다. 시간 budget은 500,000 primitive operations, auxiliary memory budget은 1 MiB다.

   문제

   pairwise·sort-scan·hash-set·bitset 중 semantic contract와 두 budget을 만족하는 후보를 모두 고르고, 지금 조건에서 가장 단순하게 방어 가능한 기본 후보 하나를 선택하세요. Big-O 기호만 쓰지 말고 탈락·보류 이유를 함께 적으세요.

   제공 자료

   • pairwise는 n(n-1)/2 equality comparisons, O(1) auxiliary space, input mutation 없음
   • sort-scan은 copied input을 정렬한 뒤 adjacent scan, 약 n⌈log2 n⌉+n comparisons/moves, 8n bytes 이상
   • hash-set은 expected 약 2n hash/lookup operations, implementation overhead를 포함해 보수적으로 32n bytes
   • bitset은 integer domain U=1,000,000,000을 초기화/주소화하며 ⌈U/8⌉ bytes가 필요

   비교표 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기정답과 비교
2. 02

   먼저 생각하기 · 기초

   cx64 predict · 중복 탐지 제약·비용·실측 관측소: “AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다.” 조건에서 비용·메모리·판정이 어떻게 바뀔지 실행 전에 봉인한다.

   상황

   n이 커지는 repeated duplicate-check service다. AI가 실행 전에 hash-set이 가장 빠르다고 제안했다.

   문제

   n=1,024에서 32,768로 증가할 때 pairwise·sort-scan·hash-set의 operation growth를 실행 전에 예측하고, 어떤 관찰이 예측을 반증할지 적으세요. 예측은 expected와 worst case를 분리해야 합니다.

   제공 자료

   • pairwise worst comparisons = n(n-1)/2
   • sort-scan modeled work = n⌈log2 n⌉+n
   • hash-set expected work = 2n, collision-adversarial worst comparisons = n(n-1)/2
   • 같은 frozen input family와 runtime manifest로 네 scale을 반복 측정한다.

   비교표 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기움직임과 비교
3. 03

   순서 따라가기 · 익힌 것을 써보기

   cx64 trace · 중복 탐지 제약·비용·실측 관측소: duplicate detection → constraint observatory → final verdict 순서로 입력 계약에서 4×4×4=64-state constraint observatory trace와 final-only verdict까지 최초 비용 모델 이탈을 추적한다.

   상황

   AI가 작성한 pairwise duplicate detector가 안쪽 loop를 항상 0부터 시작해 자기 자신과 대칭 쌍까지 비교한다.

   문제

   정상 all-pairs 구현과 AI 구현의 iteration domain을 trace하고, n=4 exact comparison count·correctness 증상·일반식 차이를 작성하세요. 최초 잘못된 loop bound만 수정하세요.

   제공 자료

   • 정상 domain: 0 ≤ i < j < n
   • AI domain: 0 ≤ i < n, 0 ≤ j < n
   • 중복은 서로 다른 두 위치의 값이 같은 경우에만 true
   • 두 구현 모두 foundDuplicate를 누적하며 configured iteration domain을 끝까지 순회한 뒤 반환한다. early return은 없다.

   순서대로 적기 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기움직임과 비교
4. 04

   내 말로 설명하기 · 익힌 것을 써보기

   cx64 explain · 중복 탐지 제약·비용·실측 관측소: 같은 중복 탐지 semantics 아래 scenario·strategy·scale을 봉인하고 exact/expected/worst cost·space·domain 전제·budget을 함께 판정한다.이 필요한 이유와 4×4×4=64-state constraint observatory trace와 final-only verdict만으로 입증할 수 없는 범위를 설명한다.

   상황

   일반 hashable key에 대한 duplicate detector를 설계한다. service는 평상시 input과 untrusted adversarial input을 모두 받는다.

   문제

   hash-set 전략의 expected O(n)과 worst O(n²), auxiliary O(n)을 비전문가도 오해하지 않도록 설명하고, 어떤 evidence가 있어야 운영 승인할지 작성하세요.

   제공 자료

   • hash lookup/insert 평균 비용은 hash distribution과 implementation policy에 의존
   • untrusted key가 collision 또는 expensive hash/equality를 유발할 수 있음
   • 정확성·time budget·memory budget·fallback이 모두 운영 contract에 포함

   까닭을 함께 쓰는 설명 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기설명 기준과 비교
5. 05

   빈칸 채우기 · 익힌 것을 써보기

   cx64 complete · 중복 탐지 제약·비용·실측 관측소: 누락된 입력 차원·비용 단위·경계 또는 판정 칸을 채워 “pairwise·sort-scan·hash-set·bitset 네 전략을 네 scenario와 네 scale에서 비교해 accept·revise·reject한다.”을 완성한다.

   상황

   bounded integer telemetry ID U=65,536에서 n=32,768개의 ID 중 duplicate를 찾는다. 8 MiB memory와 3,000,000 operation budget이 있다.

   문제

   누락된 decision worksheet를 완성하세요: 각 후보의 domain fit, modeled operations, auxiliary bytes, worst/expected caveat, verdict. bitset 초기화 비용과 hash table overhead를 생략하지 마세요.

   제공 자료

   • pairwise worst comparisons = n(n-1)/2
   • sort-scan modeled operations = n⌈log2 n⌉+n; copied payload = 8n bytes
   • hash-set expected operations = 2n; conservative entry storage = 32n bytes
   • bitset operations = n+⌈U/64⌉ word initialization; storage = ⌈U/8⌉ bytes

   비교표 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기답과 설명 함께 비교
6. 06

   틀린 곳 고치기 · 익힌 것을 써보기

   cx64 debug · 중복 탐지 제약·비용·실측 관측소: AI가 만든 분석에 “AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다.” 반례를 주입하고 최초 잘못된 가정만 수정한다.

   상황

   AI가 `len(set(values)) != len(values)` 구현과 ‘O(1) because set lookup is constant’라는 설명, 그리고 normal integer 예제 두 개를 함께 생성했다.

   문제

   이 산출물의 최초 contract/complexity 위반을 진단하고 최소 수정된 분석·독립 테스트 계획·사람 verdict를 작성하세요. 코드를 무조건 교체하지 말고 어떤 조건에서 수용 가능한지 구분하세요.

   제공 자료

   • input은 한 번만 순회 가능한 iterable일 수도 있음
   • keys는 unhashable 또는 adversarial hash/equality를 가질 수 있음
   • 서비스 memory budget과 early-exit 요구가 있음
   • AI가 코드·복잡도 설명·tests를 같은 응답에서 생성

   까닭을 함께 쓰는 설명 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기답과 설명 함께 비교
7. 07

   직접 만들기 · 새 문제

   cx64 implement · 중복 탐지 제약·비용·실측 관측소: pairwise·sort-scan·hash-set·bitset 네 전략을 네 scenario와 네 scale에서 비교해 accept·revise·reject한다.을 frozen synthetic input family에 적용해 4×4×4=64-state constraint observatory trace와 final-only verdict를 생성한다.

   상황

   브라우저나 로컬 judge에서 외부 network 없이 네 duplicate 전략의 decision을 재현하는 deterministic evaluator를 구현한다.

   문제

   입력 `(scenario, strategy, n, U, timeBudgetOps, memoryBudgetBytes)`를 받아 semantic fit·modeled work·memory·assumption·verdict를 반환하는 순수 함수를 작성하세요. wall-clock은 verdict에 사용하지 말고 integer-safe 계산과 invalid input을 처리하세요.

   제공 자료

   • strategies: pairwise, sort-scan, hash-set, bitset
   • verdict order: CONTRACT_BREACH → TIME_BUDGET_BREACH → MEMORY_BUDGET_BREACH → ASSUMPTION_GAP → MODEL_FIT
   • hash-set adversarial scenario는 worst work를 verdict에 사용
   • bitset은 integer keys and 0 ≤ key < U가 보장될 때만 semantic fit

   컴퓨터 안내와 나온 결과 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기정답과 비교
8. 08

   새 문제에 써보기 · 새 문제

   cx64 transfer · 중복 탐지 제약·비용·실측 관측소: 중복 업로드 차단·event deduplication·inventory validation로 판단을 옮겨 보존할 invariant와 달라지는 비용 모델을 방어한다.

   상황

   중복 파일 업로드 차단기를 event deduplication service로 옮긴다. event는 24시간 window, at-least-once delivery, 50M/day, 256 MiB memory, false positive 금지 요구를 가진다.

   문제

   교실의 in-memory duplicate detector를 그대로 복사하지 말고 보존할 invariant, 새 입력 차원, 후보 전략, time-space-I/O trade-off, failure/recovery evidence, AI 사용 경계를 포함한 전이 decision memo를 작성하세요.

   제공 자료

   • event key와 24시간 window가 duplicate semantics를 정의
   • n=50M/day 외에도 arrival rate r, retention window w, key bytes k, storage latency가 독립 차원
   • process restart와 partition replay 뒤에도 dedup state가 필요
   • false positive는 허용되지 않고 delayed event 정책을 명시해야 함

   까닭을 함께 쓰는 설명 · 관찰 → 규칙 → 결론 순서20자 이상 작성한 뒤 내 답과 맞춰 볼 기준을 확인하세요.

   정답 대신 4단계 힌트 보기

   1. 관찰

      AI가 hash set은 O(n)이라며 collision·memory·unhashable key·bounded domain 대안을 누락한다. 직전까지 참이었던 입력 계약과 처음 달라진 관찰값을 찾으세요.

   2. 개념

      duplicate detection·constraint observatory·final verdict를 정의·가정·관찰로 나눠 적으세요.

   3. 다음 도움

      내 생각을 먼저 적고 ‘내 답과 맞춰 볼 기준 보기’을 누르면, 풀 순서와 더 자세한 도움을 열어 드려요.

   내 답과 맞춰 볼 기준 보기설명 기준과 비교

8개 답이 남았습니다.