Gold 64상태 discipline trace 감사실

1. 01

   찾아보기 · 기초

   sq64 recognize · Gold 64상태 discipline trace 감사실: 64-state discipline·operation trace axis·boundary witness 표식 중 “discipline 4개, operation trace 4개, scale 4개의 64상태에서 removal order·endpoint·empty/full·wrap·cost를 비교하되 추상 모델을 언어별 runtime 보장으로 등치하지 않는다.”과 같은 discipline 계약을 고른다.

   상황

   세 개의 독립 저장 계약을 분류한다. undo 기록은 가장 최근 action을 먼저 되돌리고, print 작업은 승인된 순서대로 처리하며, viewport cache는 양끝에서 새 page를 넣거나 오래된 page를 제거한다. 각 저장소는 capacity 4다.

   문제

   각 저장소에 stack·queue·deque 중 맞는 ADT를 배정하고 허용 operation, 반환 순서, empty/full 실패 결과를 표로 작성하세요. 구현 container 이름이나 wall-clock 속도가 아니라 관찰 가능한 계약으로 판정하세요.

   제공 자료

   • undo는 push(action)과 pop()만 공개하며 마지막에 push한 미취소 action을 먼저 반환해야 한다.
   • print 저장소는 enqueue(job) 순서를 보존하고 dequeue()가 가장 먼저 승인된 미처리 job을 반환해야 한다.
   • viewport cache는 pushFront·pushBack·popFront·popBack을 모두 허용하고 같은 끝의 push/pop 규칙을 명시해야 한다.
   • empty 제거는 세 저장소 모두 UNDERFLOW를 반환하고 state를 바꾸지 않는다.
   • full 추가는 세 저장소 모두 OVERFLOW를 반환하고 기존 원소를 덮어쓰지 않는다. overwrite 정책은 별도 계약이다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

   먼저 생각하기 · 기초

   sq64 predict · Gold 64상태 discipline trace 감사실: “stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다.” 조건에서 반환값·상태·overflow/underflow 판정을 실행 전에 봉인한다.

   상황

   capacity 5의 language-neutral circular queue R을 예측한다. R은 buffer=[_,_,_,_,_], head=0, tail=0, size=0에서 시작하고 enqueue A,B,C, dequeue, enqueue D,E, dequeue, enqueue F,G,H를 순서대로 수행한다.

   문제

   각 command 뒤 반환값, head, tail, size, physical buffer와 head부터 읽은 logical FIFO order를 표로 예측하세요. wrap과 overflow를 구분하고 H 처리 뒤 state가 왜 유지되는지 설명하세요.

   제공 자료

   • enqueue(x)는 size=capacity이면 OVERFLOW를 반환하고 아무 field도 바꾸지 않는다.
   • 그 외 enqueue는 buffer[tail]=x, tail=(tail+1) mod capacity, size+=1 순서로 수행한다.
   • dequeue는 size=0이면 UNDERFLOW를 반환하고 아무 field도 바꾸지 않는다.
   • 그 외 dequeue는 buffer[head]를 반환하고 head=(head+1) mod capacity, size-=1로 갱신한다. 제거 slot의 stale 값은 logical order에 포함하지 않는다.
   • head=tail만으로 empty와 full을 판정하지 않고 size를 함께 사용한다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

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

   sq64 trace · Gold 64상태 discipline trace 감사실: 64-state discipline → operation trace axis → boundary witness 순서로 64셀 trace matrix·boundary witnesses·source-level ledger·accept/revise/reject memo가 만들어질 때까지 논리 순서를 추적한다.

   상황

   synthetic bar heights [4,2,2,5,1,3]에서 각 위치 왼쪽의 가장 가까운 strictly smaller 위치를 찾는다. answer가 없으면 -1이며 stack에는 아직 후보인 index를 저장한다.

   문제

   i=0부터 5까지 현재 값, pop한 index, answer, push 뒤 stack(index:value)을 추적하세요. equal height를 왜 pop하는지와 전체 work가 O(n)인 이유를 loop 중첩 모양이 아닌 element lifetime으로 설명하세요.

   제공 자료

   • 새 값 x를 처리할 때 stack top 값이 x 이상인 동안 pop한다.
   • pop 뒤 stack이 비어 있지 않으면 top index가 answer이고, 비어 있으면 -1이다.
   • answer를 기록한 뒤 현재 index를 정확히 한 번 push한다.
   • stack의 값은 bottom에서 top으로 strictly increasing해야 한다.
   • 한 index는 한 번 push되고 이후 최대 한 번 pop된다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

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

   sq64 explain · Gold 64상태 discipline trace 감사실: discipline 4개, operation trace 4개, scale 4개의 64상태에서 removal order·endpoint·empty/full·wrap·cost를 비교하되 추상 모델을 언어별 runtime 보장으로 등치하지 않는다.이 필요한 이유와 64셀 trace matrix·boundary witnesses·source-level ledger·accept/revise/reject memo만으로 보장할 수 없는 concurrency·runtime 범위를 설명한다.

   상황

   stream scores [2,1,3,3,0,2]의 모든 길이 3 window maximum을 구한다. monotonic deque는 index를 저장하며 값은 front에서 back으로 non-increasing이고 equal score의 오래된 index를 유지한다.

   문제

   각 index 처리에서 expired front 제거, dominated back 제거, push, 현재 maximum을 설명하세요. 일반 FIFO queue나 stack만으로 같은 invariant를 직접 유지할 수 없는 이유와 strict back-pop tie policy의 결과를 함께 쓰세요.

   제공 자료

   • index i를 처리하기 전에 front≤i-3인 index를 window 밖으로 보고 popFront한다.
   • 그 뒤 deque back 값이 current value보다 작은 동안 popBack한다. equal value는 남긴다.
   • 현재 index를 pushBack하고 i≥2이면 deque front 값이 window maximum이다.
   • deque에는 아직 window 안에 있고 미래 maximum 후보가 될 수 있는 index만 남는다.
   • 각 index는 한 번 pushBack되고 front 또는 back에서 최대 한 번 제거된다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

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

   sq64 complete · Gold 64상태 discipline trace 감사실: 누락된 endpoint·size·capacity·ordering·failure 칸을 채워 “각 셀의 logical sequence, 반환값, endpoint, capacity result, work와 claim level을 완성한다.”을 완성한다.

   상황

   directed synthetic graph의 adjacency order를 S:[A,B], A:[C,D], B:[D,E], C:[F], D:[F], E:[], F:[]로 봉인한다. source S에서 BFS frontier worksheet를 완성한다.

   문제

   각 dequeue 뒤 새로 enqueue한 vertex, queue front→back, visited, parent, distance를 채우고 최종 dequeue order를 쓰세요. visited를 enqueue 시점에 기록하는 이유와 stack으로 바꿀 때 보장하지 못하는 것을 설명하세요.

   제공 자료

   • 초기 parent[S]=null, distance[S]=0, visited={S}, queue=[S]다.
   • dequeue한 u의 neighbor를 주어진 adjacency 순서로 보고, 아직 visited가 아닌 v는 즉시 visited에 넣은 뒤 parent와 distance를 기록하고 enqueue한다.
   • 이미 visited인 vertex는 다시 enqueue하거나 parent를 덮어쓰지 않는다.
   • unweighted graph에서 이 FIFO frontier contract는 처음 기록한 distance를 source로부터의 최소 edge 수로 만든다.
   • stack frontier는 다른 탐색 순서를 만들 수 있으므로 이 BFS distance oracle로 자동 대체하지 않는다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

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

   sq64 debug · Gold 64상태 discipline trace 감사실: AI가 만든 구현에 “stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다.”를 주입하고 최초 잘못된 state transition만 수정한다.

   상황

   AI가 capacity N ring queue 초안을 제안했다. enqueue는 `buffer[tail]=x; tail=(tail+1)%N; if tail==head then head=(head+1)%N; return OK`, dequeue는 empty check 없이 `x=buffer[head]; head=(head+1)%N; return x`다. AI 설명은 lossless bounded FIFO와 자동 backpressure를 보장한다고 주장한다.

   문제

   초안의 FIFO·overflow·underflow·backpressure claim을 audit하고 최소 counterexample를 쓰세요. size를 둔 reject-on-full 수정 계약과 drop-oldest가 허용되는 별도 계약을 구분하고, 실패 시 state 보존 test를 제시하세요.

   제공 자료

   • 현재 요구는 accepted item을 drop하거나 overwrite하지 않는 lossless FIFO다.
   • capacity에 도달한 enqueue는 FULL_RETRY를 반환해 producer가 나중에 재시도하게 하며 queue state를 바꾸지 않아야 한다.
   • empty dequeue는 EMPTY를 반환하고 stale buffer value를 읽거나 index를 이동하지 않아야 한다.
   • head와 tail만 같을 때 empty인지 full인지 구분하려면 size, reserved slot 또는 별도 full flag가 필요하다.
   • drop-oldest는 유효한 telemetry policy가 될 수 있지만 dropped count와 loss 허용을 계약해야 하며 lossless backpressure와 같지 않다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

   직접 만들기 · 새 문제

   sq64 implement · Gold 64상태 discipline trace 감사실: 각 셀의 logical sequence, 반환값, endpoint, capacity result, work와 claim level을 완성한다.을 frozen synthetic operation stream에 적용해 64셀 trace matrix·boundary witnesses·source-level ledger·accept/revise/reject memo를 생성한다.

   상황

   language-neutral bounded circular deque DQ/1 evaluator를 구현한다. capacity 4에서 pushBack A,B,C, popFront, popFront, pushBack D,E, pushFront B, pushBack F를 실행하는 공개 trace가 있다.

   문제

   순수 함수 `evaluateDeque(capacity, commands)`를 구현하세요. pushFront·pushBack·popFront·popBack의 modulo state transition, validation, event schema와 invariant를 명시하고 공개 trace의 physical/logical final state를 계산하세요.

   제공 자료

   • state는 fixed buffer, head, size다. logical offset j의 physical index는 (head+j) mod capacity다.
   • pushFront(x)는 full이 아니면 head=(head-1+capacity) mod capacity에 x를 쓰고 size를 늘린다.
   • pushBack(x)는 full이 아니면 index=(head+size) mod capacity에 x를 쓰고 size를 늘린다.
   • popFront는 empty가 아니면 buffer[head]를 반환하고 head=(head+1) mod capacity, size-=1로 갱신한다. popBack은 index=(head+size-1) mod capacity의 값을 반환한 뒤 size를 줄인다.
   • full push는 FULL, empty pop은 EMPTY event를 반환하고 state를 바꾸지 않는다. 매 step 뒤 0≤size≤capacity와 logical order를 검사한다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

   새 문제에 써보기 · 새 문제

   sq64 transfer · Gold 64상태 discipline trace 감사실: 교차 언어 discipline shiproom·AI 생성 queue 설계 감사로 판단을 옮겨 보존할 discipline과 달라지는 failure·concurrency·cost 경계를 방어한다.

   상황

   offline device gateway의 한 partition이 accepted event를 FIFO로 전달한다. queue capacity는 1,000, high watermark 800, low watermark 500이다. accepted event는 drop·reorder할 수 없고 consumer ack 뒤에만 processed로 이동한다.

   문제

   AI 도구 없이 먼저 acceptance·conservation·failure tests와 초기 queue 정책을 쓰세요. 이후 AI가 제안한 unbounded queue와 drop-oldest ring을 audit하고, bounded FIFO·PAUSE/RESUME hysteresis·retry ownership·관측 지표를 포함한 review 설계를 제시하세요.

   제공 자료

   • conservation invariant는 `accepted = processed + queued`이며 retry 요청은 accepted가 아니다.
   • enqueue 성공 뒤 occupancy가 800 이상이면 PAUSE를 발행하고, paused 상태에서는 occupancy가 500 이하가 된 뒤에만 RESUME한다.
   • capacity 1,000에서 새 event는 FULL_RETRY를 반환하고 queue·accepted count를 바꾸지 않는다.
   • consumer는 FIFO front만 처리하며 ack 전 failure는 같은 front event를 retry할 수 있다. duplicate side effect 방지는 별도 idempotency contract가 필요하다.
   • unbounded queue는 memory bound를 만족하지 않고 drop-oldest는 lossless conservation을 깨므로 현재 기본 후보가 아니다.
   • 결과는 synthetic review evidence이며 실제 deployment throughput, 대회 성과, 자격·채용 결과를 보장하지 않는다.

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

   정답 대신 4단계 힌트 보기

   1. 관찰

      stack/FIFO/deque/bounded-ring 추상 상태를 Python·C++·Java·Rust의 직접 타입·동시성·성능 보장으로 복사한다. 직전까지 참이었던 logical order와 처음 달라진 endpoint·size·result를 찾으세요.

   2. 개념

      64-state discipline·operation trace axis·boundary witness를 discipline·boundary·source-level로 나눠 적으세요.

   3. 다음 도움

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

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

8개 답이 남았습니다.