누적 상태
4(b)는 초기 그림이 아니라 4(a) 연산이 끝난 구조를 입력으로 사용합니다. 기존 67 tower와 모든 pointer는 그대로 남습니다.
아주 작은 예: 시작 L1은 −∞,47,67,95입니다.
4. Probabilistische Datenstrukturen (4 Punkte)
4(b) · 19 삽입 — 연속 승격과 기존 67 구조 보존하기
선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.
- 용어: 기호와 전제
- 직관: 비유와 작은 예
- 풀이: 실제 상태 변화
- 확인: 검산과 자가점검
자료의 성격과 정확성 경계
문제 문언, 초기 그림, p와 난수열은 SoSe 2025 시험 기억 복기(reconstructed) 자료이며 공식 시험지나 공식 답안이 아닙니다. 구조·검색·삽입 알고리즘은 SoSe 2026 현재 강의로 검증했고, ‘난수가 p보다 작으면 승격’ 규칙과 유사 연산은 공식 Übung Sheet08 해설로 교차 확인했습니다. 그림의 정답은 이 명시된 난수 convention과 누적 상태 \(4(a)\to 4(b)\to 4(c)\)4(a)→4(b)→4(c)를 전제로 합니다.
문제를 읽기 전에 알아둘 기호와 용어
기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.
| 기호·용어 | 뜻 | 작은 예 |
|---|---|---|
| 항목 (Level 0 (L0)) | 모든 실제 key가 빠짐없이 있는 가장 아래의 완전한 정렬 리스트입니다. | 초기 L0: −∞,13,21,47,66,95 |
| 항목 (−∞ / head) | 모든 key보다 작은 sentinel node이며 각 level의 탐색 시작점입니다. 실제 저장 key가 아닙니다. | 검색은 −∞@L2에서 시작 |
| 항목 (tower) | 같은 key의 node가 Level 0부터 어떤 최고 level까지 수직으로 연결된 묶음입니다. | 초기 key 47은 L0,L1,L2의 세 node |
| 항목 (next / down) | next는 같은 level에서 오른쪽 node, down은 같은 tower의 바로 아래 node를 가리키는 pointer입니다. | 47@L1.down=47@L0 |
| 빈 포인터 (nil) | 더 이동할 node가 없음을 나타내는 값입니다. L0에서 \(\text{down}=\text{nil}\)down=nil이 되면 검색 실패입니다. | 13@L0에서 \(\text{down}=\text{nil}\)down=nil |
| 항목 (p, r) | p는 승격 확률, r은 [0,1)에서 받은 난수입니다. 이 페이지의 규칙은 \(r<p\)r<p이면 한 층 승격입니다. | \(0.15<0.33\)0.15<0.33이므로 67을 L1에 추가 |
먼저 문제의 정체를 줄글로 이해하기
이번 삽입은 반드시 4(a)의 결과에서 시작합니다. 즉 67 tower가 Level 0과 Level 1에 이미 존재합니다. 각 소문제를 독립 초기 그림에서 다시 시작하면 오답입니다.
19의 Level 0 위치는 13과 21 사이입니다. 0.09와 0.18이 연속으로 p보다 작아 Level 1과 Level 2에도 복사본이 생기고, 0.39에서 실패하여 새 Level 3은 만들지 않습니다.
최종 Level 2의 순서는 −∞,19,47입니다. 높은 Level에서도 key 정렬 순서는 항상 유지되어야 합니다.
필요한 개념을 깊게 배우기
0단계 · 이전 결과를 이어받는 누적 상태
연속 소문제는 이전 결과를 input으로 사용합니다. 4(a) 뒤 L1에는 47,67,95가 있고 L0에는 13,21,47,66,67,95가 있습니다.
19를 넣어도 기존 key나 tower는 삭제하거나 다시 추첨하지 않습니다. 새 key 19의 tower만 추가합니다.
수식으로 정확히 쓰기
핵심 규칙S_{4(b),\mathrm{start}}=S_{4(a),\mathrm{result}}
1단계 · 바로 앞 노드(predecessor) 경로
top에서 19를 찾으면 Level 2의 next 47이 너무 크므로 아래로 내려갑니다. Level 1에서도 47이 커서 내려가고 Level 0에서 13까지 오른쪽으로 간 뒤 21 앞에 멈춥니다.
따라서 각 Level의 삽입 predecessor는 L0의 13, L1의 −∞, L2의 −∞입니다.
수식으로 정확히 쓰기
\[\mathrm{update}[0]=13\]
\mathrm{update}[0]=13\[\mathrm{update}[1]=-\infty\]
\mathrm{update}[1]=-\infty\[\mathrm{update}[2]=-\infty\]
\mathrm{update}[2]=-\infty2단계 · 두 번 연속 승격 성공
\(0.09<0.33\)0.09<0.33이므로 \(L1, 0.18<0.33\)L1, 0.18<0.33이므로 L2까지 올라갑니다. 성공할 때마다 다음 난수 하나를 더 읽습니다.
\(0.39\ge 0.33\)0.39≥0.33에서 첫 실패가 나와 종료합니다. 사용한 난수는 정확히 세 개이며 나머지는 그대로 남깁니다.
수식으로 정확히 쓰기
\[0.09<p\Longrightarrow L_{1}\]
0.09<p\Longrightarrow L₁\[0.18<p\Longrightarrow L_{2}\]
0.18<p\Longrightarrow L₂핵심 규칙0.39\ge p\Longrightarrow\text{중단}
3단계 · 새 최고층이 필요한가
기존 최고 Level은 2이고 19도 Level 2까지만 올라가므로 전체 높이는 변하지 않습니다. 만약 Level 2 승격 뒤 다음 난수도 성공했다면 새 Level 3 head와 19를 만들어야 합니다.
이 문제에서는 0.39가 실패이므로 Level 3을 그리면 안 됩니다.
수식으로 정확히 쓰기
\[h_{\mathrm{old}}=2\]
h_{\mathrm{old}}=2\[h_{19}=2\Longrightarrow h_{\mathrm{new}}=2\]
h₁₉=2\Longrightarrow h_{\mathrm{new}}=2이 소문제를 왜 배우나
연속 소문제에서는 앞 단계의 결과가 다음 입력입니다. 19 삽입은 기존 67 tower를 보존하면서 두 번 연속 승격하고, 새 최고 level을 만들지 않는 경계까지 판단하는 누적 상태 연습입니다.
- 4(a)의 결과를 정확히 시작 상태로 옮기고 기존 node를 삭제하거나 다시 추첨하지 않을 수 있습니다.
- 각 level의 predecessor를 top-down search 중 저장하고 19 tower를 L0부터 L2까지 연결할 수 있습니다.
- 성공 두 번과 첫 실패 한 번만 소비해 전체 난수열의 used/unused를 정확히 표시할 수 있습니다.
풀이 전에 꼭 알아야 할 말
위에서 아래로 찾는 바로 앞 노드 탐색(top-down predecessor search)
최고 층에서 목표를 넘지 않는 데까지 오른쪽으로 가고, 넘을 다음 노드 앞에서 아래로 내려가며 각 층의 현재 노드를 update에 저장합니다.
아주 작은 예: 19 앞의 update는 L2=−∞, L1=−∞, \(L0=13\)
L0=13입니다.새 최고 층(level)
새 키가 기존 최고 층보다 한 층 더 승격될 때만 새 머리 층(head level)을 만듭니다. 기존 최고 층까지만 올라가면 높이는 그대로입니다.
아주 작은 예: 기존 \(\max=2\)
max=2이고 19의 \(\text{top}=2\)top=2라 L3을 만들지 않습니다.첫 실패까지 난수 사용(first failure consumption)
승격을 중단시킨 실패 난수도 읽어서 사용한 값입니다. 그 다음 값부터 미사용입니다.
아주 작은 예: 0.09,0.18,0.39는 사용했고 0.06은 사용하지 않았습니다.
운행 중인 노선에 새 역을 누적 공사하기
67번 급행역을 이미 만든 지하철 지도에 19번 역을 추가합니다. 기존 역은 철거하지 않고, 19의 위치만 각 노선에서 찾습니다. 두 번 추첨에 성공해 일반선·급행선·특급선에 19가 생기고 세 번째 실패에서 공사를 끝냅니다.
이미 운행 중인 67번 급행역
↔
4(a)에서 만든 67@L0,L1 tower
각 노선의 19 직전 역
↔
update[0]=13, update[1]=−∞, update[2]=−∞
두 번 연속 공사 승인
↔
\(0.09,0.18<p\)
0.09,0.18<p로 L1,L2 승격새 노선 증설 불허
↔
\(0.39\ge p\)
0.39≥p라 L3 없음비유의 한계: 각 level의 19 node는 별개의 위치에 그려도 하나의 tower로 수직 정렬되어야 합니다. 기존 67 node를 다시 난수로 평가하거나 위치를 바꾸는 작업은 없습니다.
누적 삽입의 상태 전이
13→19→21로 연결해 정렬된 기본 목록을 만듭니다.시작 상태를 먼저 고정하고, predecessor path와 난수 결정을 분리해 기록하면 기존 tower 누락과 불필요한 L3 생성 오류를 막을 수 있습니다.
먼저 작은 예제로 연습 · 기존 tower를 보존하며 key 3 추가
L0=[−∞,2,6], L1=[−∞,6]에 \(p=0.5,\)p=0.5,난수 0.1,0.8이 주어졌다고 가정합니다. 기존 6 tower는 그대로 둡니다.
연속 연산에서는 기존 L1의 6을 지우거나 다시 추첨하면 안 됩니다.
6@L1 ↓ 6@L0 유지\(2<3<6\)2<3<6이라 정렬 위치가 결정됩니다.
2→3→6\(0.1<0.5\)0.1<0.5이고 L1에서도 −∞<\(3<6\)3<6순서를 지킵니다.
3→6첫 실패에서 멈추므로 새 L2는 만들지 않습니다.
used 0.1,0.8 | 기존 6 tower 보존작은 예제의 결론: 새 삽입은 새 key의 tower만 더하며, 이전 연산으로 만들어진 node와 높이는 이후 난수와 무관하게 그대로 유지됩니다.
이제 실제 시험 문제에 연결
4(b)의 시작 L1에 어떤 key가 있어야 하나?
4(a) 결과이므로 −∞,47,67,95가 있어야 합니다. 67을 빼고 초기 구조로 되돌아가면 누적 상태를 잃은 오답입니다.
19를 찾을 때 왜 상위 두 level의 predecessor가 head인가?
L2와 L1 모두 head의 next가 각각 47이고 \(47>19\)47>19입니다. 오른쪽으로 가면 목표를 넘으므로 현재 head를 저장하고 아래로 내려갑니다.
L0 predecessor는 왜 13인가?
L0 head에서 \(\text{next}=13\le 19\)next=13≤19라 13까지 오른쪽으로 이동합니다. 그 다음 \(21>19\)21>19라 멈추므로 \(\text{update}[0]=13\)update[0]=13입니다.
세 난수는 각자 무엇을 뜻하나?
0.09는 L1, 0.18은 L2 승격 성공입니다. 다음 0.39는 L3 승격 실패이며 이 실패값까지 사용한 뒤 0.06 이후는 읽지 않습니다.
왜 새 L3을 만들지 않나?
L2에 도달한 뒤 L3 여부를 정하는 0.39가 p 이상이기 때문입니다. 19의 top level은 기존 max level 2와 같아 전체 높이도 변하지 않습니다.
답이 맞는지 스스로 검산
- 최종 L0,L1,L2가 각각 오름차순이고 19가 모든 아래 level에 연속으로 존재하는지 확인합니다.
- 4(a)의 67 tower와 기존 47·95 tower가 사라지거나 높이가 변하지 않았는지 before/after를 대조합니다.
- 0.09,0.18,0.39만 used이고 실패 뒤 0.06,0.01,0.32,0.67은 unused인지 확인합니다.
30초 자가점검
0.39 대신 0.20이었다면 다음에 무엇을 해야 하나?
힌트: L3 승격이 성공하면 기존 최고 level을 넘어섭니다.
정답: 새 L3 head와 19@L3을 만들고 수직 연결한 뒤 다음 난수 0.06으로 L4 여부를 계속 결정해야 합니다.
19를 넣을 때 기존 67의 tower 높이를 다시 뽑아도 되나?
힌트: 난수는 어느 key의 새 삽입에만 적용되는지 생각하세요.
정답: 안 됩니다. 난수열은 새 key 19의 tower만 결정하며 이미 저장된 67 구조는 그대로 유지합니다.
최종 L2의 올바른 순서는 무엇인가?
힌트: 19와 47의 크기를 비교하세요.
정답: −∞→\(19\to 47\)19→47입니다. 높은 level도 항상 key 오름차순을 유지합니다.
마지막에 쓰는 시험 답안 틀
4(a)의 결과에서 L0의 13과 21 사이에 19를 넣는다. \(0.09<0.33\)0.09<0.33으로 \(L1, 0.18<0.33\)L1, 0.18<0.33으로 L2에 올리고 \(0.39\ge 0.33\)0.39≥0.33에서 멈춘다. 최종 L2는 −∞→\(19\to 47\)19→47이다.
자주 하는 실수
- 초기 그림으로 되돌아가 67을 잃어버린다.
- 19를 21 뒤에 놓는다.
- 성공 두 번인데 Level 1까지만 그린다.
- 0.39 실패 후 0.06을 사용한다.
- Level 2에서 19를 47 뒤에 둔다.
- 불필요한 Level 3을 만든다.
근거와 정확성 범위
복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.
- \(\text{reconstructed}_{\text{exam}}\)
reconstructed(exam)AuD Gedächtnisprotokoll SoSe 2025.md· lines 226-244 and linked image · 신뢰도/범위: 복기 문언·이미지이며 공식 답안 아님초기 Skip List, p, 삽입 key, 난수열, 검색 target의 복기 문언
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 4-12 · 신뢰도/범위: 현재 강의 원문으로 검증정렬 리스트, express level, head/node pointer 모델, search pseudocode, 기대 level 크기
- \(\text{current}_{\text{lecture}}\)
current(lecture)Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 16-20 · 신뢰도/범위: 현재 강의 원문으로 검증삽입 predecessor 저장, 확률적 승격, 평균 검색·삽입·삭제 시간과 공간
- \(\text{official}_{\text{solution}}\)
official(solution)Übung\AuD26_Sheet08-Sol.pdf· pp. 8-10 · 신뢰도/범위: 공식 연습문제 풀이로 교차 검증\(r<p\)
r<p승격 convention, 첫 실패까지 난수 소비, 성공·실패 검색 path와 누적 삽입 예시
마지막 생성: 2026-08-02 08:51