4. Probabilistische Datenstrukturen (4 Punkte)

4(a) · 67 삽입 — 검색 위치와 확률적 탑(tower) 높이를 분리해서 계산하기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

문제 문언, 초기 그림, 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에 추가

먼저 문제의 정체를 줄글로 이해하기

Skip List 삽입은 두 작업의 결합입니다. 먼저 일반 정렬 리스트처럼 Level 0에서 key가 들어갈 위치를 찾고, 그다음 난수를 하나씩 소비해 같은 key의 복사본을 위층에 더 만들지 결정합니다.

확률 \(p=0.33\)p=0.33은 '난수가 0.33보다 작으면 승격'으로 사용합니다. 첫 실패가 나오면 즉시 멈추며 뒤의 난수는 사용하지 않습니다. Level 0 삽입 자체에는 난수가 필요 없습니다.

67은 66과 95 사이에 들어갑니다. 첫 난수 \(0.15<0.33\)0.15<0.33이므로 Level 1에도 67을 만들고, 다음 \(0.80\ge 0.33\)0.80≥0.33이므로 Level 2에는 만들지 않습니다.

필요한 개념을 깊게 배우기

개념 1

0단계 · 스킵 리스트(Skip List)의 층

Level 0은 모든 실제 key가 있는 완전한 정렬 리스트입니다. 위 Level은 아래 원소 중 일부만 확률적으로 복사한 express lane입니다.

한 key가 Level h에 있으면 Level 0부터 h까지 끊김 없이 tower를 이룹니다. Level 2에만 있고 Level 1에 없는 식의 구멍은 만들지 않습니다.

수식으로 정확히 쓰기

\[L_{0}=\{\text{모든 실제 키}\}\]L₀=\{\text{모든 실제 키}\}

핵심 규칙x\in \(L_{h}\)Lₕ\Longrightarrow x\in \(L_{0}\)L₀,\(L_{1}\)L₁,\\(\text{ldots},L_{h-1}\)ldots,Lₕ-1}

개념 2

1단계 · 정렬 위치 찾기

67보다 작은 가장 큰 key는 66이고, 다음 key는 95입니다. 따라서 Level 0에서 66.next를 67로, 67.next를 95로 연결합니다.

탐색 중 각 Level의 predecessor를 저장하면 승격할 때 다시 처음부터 찾지 않고 그 predecessor 뒤에 위층 복사본을 연결할 수 있습니다.

수식으로 정확히 쓰기

\[66<67<95\]66<67<95

핵심 규칙\mathrm{update}[0]=66,\quad\mathrm{update}[1]=47,\quad\\(\text{mathrm}{\text{update}}[2]=47\)mathrm{update}[2]=47

개념 3

2단계 · 난수와 승격

Level 0에 넣은 뒤 첫 난수로 Level 1 승격 여부를 결정합니다. 성공하면 다음 난수로 Level 2를 결정하고, 실패하면 그 즉시 tower 생성이 끝납니다.

여기서는 \(0.15<0.33\)0.15<0.33이 성공, \(0.80\ge 0.33\)0.80≥0.33이 실패입니다. 그러므로 67의 tower 높이는 최고 Level 1입니다.

수식으로 정확히 쓰기

\[0.15<p\Longrightarrow\text{1층으로 승격}\]0.15<p\Longrightarrow\text{1층으로 승격}

핵심 규칙0.80\ge p\Longrightarrow\text{2층 전에 중단}

개념 4

3단계 · 기대 성능

각 키(key)가 i층까지 올라갈 확률은 p의 i제곱이므로 기대 층 크기는 \(n,\text{pn},p^{2}n\)n,pn,p²n처럼 줄어듭니다. 이 기하급수 감소가 평균 높이와 탐색 시간을 \(\Theta(\log_{1/p} n)\)Θ(log₁/p} n)으로 만듭니다.

한 번의 구체적 삽입 결과는 난수에 따라 달라도, 많은 실행의 평균에서는 높은 탑(tower)이 드물게 나타납니다.

수식으로 정확히 쓰기

핵심 규칙\Pr(H\ge i)=\(p^{i}\)p^{i},\qquad\mathbb{E}[\lvert \(L_{i}\)Lᵢ\\(\text{rvert}]=\text{np}^{i}\)rvert]=np^{i}

핵심 규칙\mathbb{E}[T_{\text{검색·삽입·삭제}}]=\Theta\!\left(\\(\log_{1/p}n\)log₁/p}n\right)

초보자용 연결 강의

이 소문제를 왜 배우나

Skip List 삽입은 정렬 위치를 찾는 결정적 단계와 tower 높이를 정하는 확률적 단계를 분리해야 합니다. 이 문제는 Level 0은 반드시 삽입하고, 위 level만 난수로 결정한다는 가장 중요한 규칙을 짧은 trace로 연습합니다.

풀이 전에 꼭 알아야 할 말

시작 표식 노드(sentinel head) −∞

각 층(level) 맨 왼쪽의 시작 노드입니다. 모든 실제 키보다 작다고 약속해 첫 키 앞 삽입과 검색을 같은 규칙으로 처리합니다.

아주 작은 예: 2층의 −∞.next는 초기에는 47입니다.

바로 앞 노드(predecessor) update[level]

새 키보다 작으면서 그 층에서 가장 오른쪽에 있는 노드입니다. 새 노드는 이 바로 앞 노드와 기존 다음 노드(next) 사이에 연결됩니다.

아주 작은 예: 0층에서 \(66<67<95\)66<67<95이므로 \(\text{update}[0]=66\)update[0]=66입니다.

탑(tower) 연속성

키가 h층에 있다면 같은 키가 0층부터 h층까지 모든 아래 층에 있어야 합니다. 중간 층을 건너뛴 복사본은 허용하지 않습니다.

아주 작은 예: 67이 1층에 있으면 반드시 67@L1.down=67@L0입니다.

승격 사건 \(r<p\)r<p

L0 삽입 뒤 난수 r이 p보다 작을 때만 바로 위 level에 복사본을 만듭니다. 성공하면 다음 난수를 읽고 실패하면 종료합니다.

아주 작은 예: \(0.15<0.33\)0.15<0.33성공, 다음 \(0.80\ge 0.33\)0.80≥0.33실패입니다.

일반선 역을 만든 뒤 급행 정차 여부 추첨

67번 역은 번호 순서 때문에 일반선의 66과 95 사이에 반드시 생깁니다. 그다음 추첨에 성공하면 같은 67번 역을 급행선에도 만들고, 다시 성공하면 특급선에도 만듭니다. 첫 실패가 나오면 공사를 멈춥니다.

모든 역이 있는 일반선
↔
모든 key가 있는 Level 0
급행·특급 정차역
↔
위 level의 key 복사 node
역 번호 순서
↔
각 level의 key 오름차순
첫 탈락에서 추첨 종료
↔
첫 \(r\ge p\)r≥p뒤 난수 미사용

비유의 한계: 위 level의 역은 독립된 새 key가 아니라 아래 같은 key와 down/up pointer로 연결된 복사 node입니다. 따라서 row만 그리지 말고 tower의 수직 링크도 표시해야 합니다.

67 삽입의 다섯 장면

① 삽입 위치 검색(search)L2의 47까지 오른쪽, L1 47로 아래, L0 66까지 이동합니다.
② 0층 삽입(insert)66.next를 67로, 67.next를 95로 연결합니다.
\(③ r=0.15\)③ r=0.15\(0.15<0.33\)0.15<0.33이라 L1의 47과 95 사이에 67 복사본을 둡니다.
④ 수직 연결(vertical link)67@L1.down을 67@L0에 연결해 연속된 탑을 만듭니다.
\(⑤ r=0.80 \text{stop}\)⑤ r=0.80 stop\(0.80\ge 0.33\)0.80≥0.33이라 L2는 그대로이고 뒤 난수는 읽지 않습니다.

위에서 위치를 찾는 path와 아래에서 tower를 만드는 순서는 다릅니다. search로 update를 모은 뒤 L0를 연결하고 난수 성공 횟수만큼 위로 올라갑니다.

먼저 작은 예제로 연습 · \(p=0.5\)p=0.5에서 6 삽입

L0=[−∞,2,8], L1=[−∞,8]이고 난수는 0.2,0.7,0.1입니다. 6의 정렬 위치와 tower를 분리합니다.

L0 위치 찾기

\(2<6<8\)2<6<8이므로 2와 8 사이가 유일한 정렬 위치입니다.

L0: −∞→\(2\to [6]\to 8\)2→[6]→8
첫 난수 0.2 사용

\(0.2<0.5\)0.2<0.5라 L1에도 6 복사본을 삽입합니다.

L1: −∞→\(6\to 8\)6→8
수직 link 연결

L1의 6은 L0의 6과 같은 tower여야 하므로 down pointer를 연결합니다.

6@L1 ↓ 6@L0
둘째 난수 0.7에서 중단

\(0.7\ge 0.5\)0.7≥0.5가 첫 실패이므로 0.1은 사용하지 않습니다.

used: 0.2,0.7 | unused: 0.1

작은 예제의 결론: Level 0 삽입은 확정이고 연속 성공 횟수만 tower 높이를 결정합니다. 첫 실패까지 포함해 소비하고 그 뒤 난수는 그대로 남깁니다.

이제 실제 시험 문제에 연결

67의 L0 predecessor는 왜 66인가?

초기 L0가 −∞,13,21,47,66,95 순서이고 \(66<67<95\)66<67<95입니다. 따라서 67보다 작은 가장 큰 key 66 뒤가 삽입 위치입니다.

상위 predecessor는 무엇인가?

L1에서는 47 다음 95가 67보다 크므로 \(\text{update}[1]=47\)update[1]=47이고, L2에서는 47 다음이 없으므로 \(\text{update}[2]=47\)update[2]=47입니다. 다만 L2 삽입은 난수가 실패해 실행하지 않습니다.

첫 난수 0.15가 무엇을 결정하나?

L0 존재 여부가 아니라 L1 복사본 여부를 결정합니다. \(0.15<0.33\)0.15<0.33이므로 47과 95 사이에 67@L1을 추가합니다.

0.80 뒤 왜 0.61을 읽지 않나?

\(0.80\ge 0.33\)0.80≥0.33이 첫 실패라 tower 생성 loop가 즉시 끝납니다. 따라서 사용 난수는 0.15와 0.80뿐이고 나머지는 미사용입니다.

최종 tower와 rows는 어떻게 검산하나?

67은 L0,L1에 연속으로 있고 L2에는 없습니다. L0와 L1 모두 오름차순이며 기존 47·95 tower와 다른 key는 그대로입니다.

답이 맞는지 스스로 검산

  • L0에 초기 모든 key와 새 67이 정확히 한 번씩 있고 −∞<\(13<21<47<66<67<95\)13<21<47<66<67<95순서인지 확인합니다.
  • L1의 67이 L0의 67 바로 위 열에 있고 down/up 링크가 이어지며 L2에 고립된 67이 없는지 확인합니다.
  • 사용 난수는 첫 성공 0.15와 첫 실패 0.80 두 개뿐이고 0.61 이후는 취소선이 없는지 확인합니다.

30초 자가점검

첫 난수 0.15가 0.33보다 작지 않았다면 67은 목록에 없나?

힌트: 난수는 어느 level부터 결정하는지 떠올리세요.

정답: 아닙니다. 67은 L0에 반드시 있고, 실패했다면 위 level 복사본만 없이 tower 높이 0으로 끝납니다.

0.15,0.20,0.40 순서였다면 67의 최고 level은?

힌트: 성공할 때마다 L1, L2로 한 층씩 올라갑니다.

정답: 두 번 성공해 L2까지 있고 0.40 실패에서 멈추므로 최고 level은 2입니다.

L1에서 67을 95 뒤에 그리면 어떤 invariant가 깨지나?

힌트: 모든 level은 같은 key 순서를 따릅니다.

정답: 각 row의 오름차순 invariant가 깨집니다. \(47<67<95\)47<67<95이므로 67은 반드시 두 node 사이입니다.

마지막에 쓰는 시험 답안 틀

Level 0에서 66과 95 사이에 67을 삽입한다. \(0.15<0.33\)0.15<0.33이므로 L1에도 삽입하고, \(0.80\ge 0.33\)0.80≥0.33에서 중단한다. 사용 난수 0.15, 0.80에 취소선을 긋고 L2는 그대로 그린다.

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51