독일어 원문 제목: 4. Probabilistische Datenstrukturen (4 Punkte)

4번 · 확률적 자료구조 스킵 리스트(Skip List)

완전 초보자를 위한 구조 읽기 → 위치 찾기 → 난수 승격 → 검색 경로 → 검산

복기 원문을 구조적으로 다시 그린 초기 스킵 리스트
층 2−∞47층 1−∞4795층 0−∞1321476695
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결

선행지식 없이 시작

이 페이지를 읽는 순서

연결 리스트와 확률을 배우지 않은 학습자가 한 페이지에서 Skip List의 node, tower, level, pointer를 읽고 삽입과 검색 경로를 직접 그릴 수 있도록 구성했습니다. 먼저 정렬된 지하철 노선 비유로 구조를 읽고, 작은 tower 예제, 실제 난수 소비, 색칠된 search overlay 순서로 학습합니다.

  1. tower를 세로로 읽기

    같은 key가 여러 level에 있으면 하나의 tower입니다. 아래 Level 0에는 모든 key가 있고 위로 갈수록 일부 key만 남는다는 구조 불변식을 먼저 확인합니다.

  2. 오른쪽·아래 규칙 익히기

    항상 최고 head에서 시작합니다. next가 목표 이하이면 오른쪽, 목표를 넘거나 next가 없으면 아래로 간다는 한 규칙으로 검색 위치와 삽입 predecessor를 찾습니다.

  3. 난수는 첫 실패까지만

    Level 0 삽입은 확정이고 난수는 그 위 복사본부터 결정합니다. \(r<p\)r<p인 동안 한 level씩 올리고 첫 \(r\ge p\)r≥p에서 즉시 멈춰 미사용 난수를 보존합니다.

  4. 그림으로 검산하기

    모든 row가 정렬됐는지, 위 node가 아래 모든 level에 이어지는지, 사용 난수와 search edge가 규칙에 맞는지 체크한 뒤 힌트 문제를 풉니다.

먼저 익힐 기호와 용어

항목 (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에 추가

정확성 범위

문제 문언, 초기 그림, p와 난수열은 SoSe 2025 시험 기억 복기(reconstructed) 자료이며 공식 시험지나 공식 답안이 아닙니다. 구조·검색·삽입 알고리즘은 SoSe 2026 현재 강의로 검증했고, ‘난수가 p보다 작으면 승격’ 규칙과 유사 연산은 공식 Übung Sheet08 해설로 교차 확인했습니다. 그림의 정답은 이 명시된 난수 convention과 누적 상태 \(4(a)\to 4(b)\to 4(c)\)4(a)→4(b)→4(c)를 전제로 합니다.

삽입·검색 전체 의사코드(pseudocode)

아래 규칙을 먼저 고정해야 같은 난수와 구조에서 같은 답을 재현할 수 있습니다.

삽입(insert)

search from top head and store predecessor update[level]
insert key after update[0] on Level 0 and repair next/prev
below = the new Level-0 node
level = 1
while next random r < p:
    if level > maxLevel:
        create newHead; newHead.down = oldTopHead; oldTopHead.up = newHead
        topHead = new head; maxLevel = level; update[level] = new head
    copy = insert key after update[level] and repair next/prev
    copy.down = below; below.up = copy; below = copy
    level = level+1
stop immediately at the first r >= p

검색(search)

current = top head
while current != nil:
    if current.key == target: return current
    if current.next != nil and current.next.key <= target:
        current = current.next
    else:
        current = current.down
return nil

배점: 1점

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

\(p=0.33\)p=0.33인 초기 Skip List에 67을 삽입한다. 난수 0.15, 0.80, 0.61, 0.72, 0.82, 0.25, 0.83을 왼쪽부터 필요만큼 사용한다.

이 절은 다른 소문제를 펼치지 않아도 시작 구조, 용어, 작은 예제, 실제 풀이, 검산을 모두 확인할 수 있습니다.

먼저 문제의 정체부터 파악하기

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에는 만들지 않습니다.

4(a) 풀이 시작 구조
층 2−∞47층 1−∞4795층 0−∞1321476695
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

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

  • 최고 level부터 search 규칙을 따라 각 level의 predecessor update 값을 찾을 수 있습니다.
  • 전체 난수열에서 실제 사용한 값만 구분하고 첫 실패 뒤 값은 읽지 않을 수 있습니다.
  • 67의 L0·L1 node를 수직으로 연결하고 모든 level의 정렬 순서를 검산할 수 있습니다.

풀이 전에 알아둘 용어

시작 표식 노드(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 삽입의 다섯 장면

  1. ① 삽입 위치 검색(search)L2의 47까지 오른쪽, L1 47로 아래, L0 66까지 이동합니다.
  2. ② 0층 삽입(insert)66.next를 67로, 67.next를 95로 연결합니다.
  3. \(③ r=0.15\)③ r=0.15\(0.15<0.33\)0.15<0.33이라 L1의 47과 95 사이에 67 복사본을 둡니다.
  4. ④ 수직 연결(vertical link)67@L1.down을 67@L0에 연결해 연속된 탑을 만듭니다.
  5. ⑤ \(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를 분리합니다.

  1. L0 위치 찾기

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

    현재 상태: L0: −∞→\(2\to [6]\to 8\)2→[6]→8

  2. 첫 난수 0.2 사용

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

    현재 상태: L1: −∞→\(6\to 8\)6→8

  3. 수직 link 연결

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

    현재 상태: 6@L1 ↓ 6@L0

  4. 둘째 난수 0.7에서 중단

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

    현재 상태: used: 0.2,0.7 | unused: 0.1

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

핵심 개념을 줄글로 깊게 이해하기

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

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

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

머릿속 그림: 모든 역이 있는 일반선 위에 일부 역만 정차하는 급행선과 특급선을 쌓은 모습입니다.

\[L_0=\{\text{모든 실제 키}\}\]
\[x\in L_h\Longrightarrow x\in L_0,L_1,\ldots,L_{h-1}\]

1단계 · 정렬 위치 찾기

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

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

머릿속 그림: 새 역 67을 노선 번호 순서상 66역과 95역 사이에 끼워 넣습니다.

\[66<67<95\]
\[\mathrm{update}[0]=66,\quad\mathrm{update}[1]=47,\quad\mathrm{update}[2]=47\]

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.80\ge p\Longrightarrow\text{2층 전에 중단}\]

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},\qquad\mathbb{E}[\lvert L_i\rvert]=np^{i}\]
\[\mathbb{E}[T_{\text{검색·삽입·삭제}}]=\Theta\!\left(\log_{1/p}n\right)\]

실제 시험 문제 풀이를 단계별로 연결

  1. 67의 L0 predecessor는 왜 66인가?

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

  2. 상위 predecessor는 무엇인가?

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

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

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

  4. 0.80 뒤 왜 0.61을 읽지 않나?

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

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

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

전체 난수열: 사용값만 취소선

  1. 난수 0.15L1 승격 성공
  2. 난수 0.80L2 승격 실패, 즉시 종료
  3. 난수 0.61미사용
  4. 난수 0.72미사용
  5. 난수 0.82미사용
  6. 난수 0.25미사용
  7. 난수 0.83미사용

첫 실패값까지 사용하며, 그 뒤 값은 읽지 않습니다.

난수 판정을 첫 실패까지 계산하기

  1. 난수 \(r=0.15\)r=0.15\(0.15 < 0.33\)0.15 < 0.33성공 — Level 1에 67 추가
  2. 난수 \(r=0.80\)r=0.80\(0.80 \ge 0.33\)0.80 ≥ 0.33실패 — 승격 종료
4(a) 결과 구조
층 2−∞47층 1−∞476795층 0−∞132147666795
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결이번에 삽입한 탑(tower)

답이 맞는지 스스로 검산

  1. L0에 초기 모든 key와 새 67이 정확히 한 번씩 있고 −∞<\(13<21<47<66<67<95\)13<21<47<66<67<95순서인지 확인합니다.
  2. L1의 67이 L0의 67 바로 위 열에 있고 down/up 링크가 이어지며 L2에 고립된 67이 없는지 확인합니다.
  3. 사용 난수는 첫 성공 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는 그대로 그린다.

초보자가 자주 틀리는 지점

  • Level 0 삽입 여부까지 난수로 결정한다.
  • 0.15를 실패로 반대로 읽는다.
  • 0.80 실패 뒤에도 다음 난수를 계속 사용한다.
  • Level 1의 정렬 위치에서 95 뒤에 67을 둔다.
  • 새 key가 올라갈 때 중간 Level을 건너뛴다.
  • 사용하지 않은 난수까지 모두 지운다.

배점: 1점

4(b) · 19 삽입 — 연속 승격과 기존 67 구조 보존하기

4(a)의 결과에 19를 삽입한다. 난수 0.09, 0.18, 0.39, 0.06, 0.01, 0.32, 0.67을 왼쪽부터 사용한다.

이 절은 다른 소문제를 펼치지 않아도 시작 구조, 용어, 작은 예제, 실제 풀이, 검산을 모두 확인할 수 있습니다.

먼저 문제의 정체부터 파악하기

이번 삽입은 반드시 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 정렬 순서는 항상 유지되어야 합니다.

4(b) 풀이 시작 구조
층 2−∞47층 1−∞476795층 0−∞132147666795
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

연속 소문제에서는 앞 단계의 결과가 다음 입력입니다. 19 삽입은 기존 67 tower를 보존하면서 두 번 연속 승격하고, 새 최고 level을 만들지 않는 경계까지 판단하는 누적 상태 연습입니다.

  • 4(a)의 결과를 정확히 시작 상태로 옮기고 기존 node를 삭제하거나 다시 추첨하지 않을 수 있습니다.
  • 각 level의 predecessor를 top-down search 중 저장하고 19 tower를 L0부터 L2까지 연결할 수 있습니다.
  • 성공 두 번과 첫 실패 한 번만 소비해 전체 난수열의 used/unused를 정확히 표시할 수 있습니다.

풀이 전에 알아둘 용어

누적 상태

4(b)는 초기 그림이 아니라 4(a) 연산이 끝난 구조를 입력으로 사용합니다. 기존 67 tower와 모든 pointer는 그대로 남습니다.

아주 작은 예: 시작 L1은 −∞,47,67,95입니다.

위에서 아래로 찾는 바로 앞 노드 탐색(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를 다시 난수로 평가하거나 위치를 바꾸는 작업은 없습니다.

누적 삽입의 상태 전이

  1. ① 4(a)의 결과 상태67은 L0,L1에 이미 있고 초기의 다른 노드도 모두 유지됩니다.
  2. ② 19의 위치 찾기상위에서는 머리 노드에서 내려가고 L0에서 13 뒤에 멈춥니다.
  3. ③ 0층에 삽입\(13\to 19\to 21\)13→19→21로 연결해 정렬된 기본 목록을 만듭니다.
  4. ④ 두 번 승격 성공0.09와 0.18 성공으로 L1,L2에 19를 수직 연결합니다.
  5. ⑤ 3층 전에 중단0.39 실패라 높이는 2로 유지되고 0.06 이후는 미사용입니다.

시작 상태를 먼저 고정하고, predecessor path와 난수 결정을 분리해 기록하면 기존 tower 누락과 불필요한 L3 생성 오류를 막을 수 있습니다.

작은 예제로 먼저 연습 · 기존 tower를 보존하며 key 3 추가

L0=[−∞,2,6], L1=[−∞,6]에 \(p=0.5,\)p=0.5,난수 0.1,0.8이 주어졌다고 가정합니다. 기존 6 tower는 그대로 둡니다.

  1. 시작 구조 복사

    연속 연산에서는 기존 L1의 6을 지우거나 다시 추첨하면 안 됩니다.

    현재 상태: 6@L1 ↓ 6@L0 유지

  2. L0의 2와 6 사이에 3 삽입

    \(2<3<6\)2<3<6이라 정렬 위치가 결정됩니다.

    현재 상태: L0: −∞→\(2\to 3\to 6\)2→3→6

  3. 0.1 성공으로 L1에 3 추가

    \(0.1<0.5\)0.1<0.5이고 L1에서도 −∞<\(3<6\)3<6순서를 지킵니다.

    현재 상태: L1: −∞→\(3\to 6\)3→6

  4. 0.8 실패로 종료

    첫 실패에서 멈추므로 새 L2는 만들지 않습니다.

    현재 상태: used 0.1,0.8 | 기존 6 tower 보존

작은 예제의 결론: 새 삽입은 새 key의 tower만 더하며, 이전 연산으로 만들어진 node와 높이는 이후 난수와 무관하게 그대로 유지됩니다.

핵심 개념을 줄글로 깊게 이해하기

0단계 · 이전 결과를 이어받는 누적 상태

연속 소문제는 이전 결과를 input으로 사용합니다. 4(a) 뒤 L1에는 47,67,95가 있고 L0에는 13,21,47,66,67,95가 있습니다.

19를 넣어도 기존 key나 tower는 삭제하거나 다시 추첨하지 않습니다. 새 key 19의 tower만 추가합니다.

머릿속 그림: 첫 공사로 만든 67번 급행역을 그대로 둔 채 19번 역을 추가 공사합니다.

\[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의 −∞입니다.

머릿속 그림: 각 노선에서 19역 바로 앞 역을 메모해 두었다가 tower 연결점으로 사용합니다.

\[\mathrm{update}[0]=13\]
\[\mathrm{update}[1]=-\infty\]
\[\mathrm{update}[2]=-\infty\]

2단계 · 두 번 연속 승격 성공

\(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.18<p\Longrightarrow L_2\]
\[0.39\ge p\Longrightarrow\text{중단}\]

3단계 · 새 최고층이 필요한가

기존 최고 Level은 2이고 19도 Level 2까지만 올라가므로 전체 높이는 변하지 않습니다. 만약 Level 2 승격 뒤 다음 난수도 성공했다면 새 Level 3 head와 19를 만들어야 합니다.

이 문제에서는 0.39가 실패이므로 Level 3을 그리면 안 됩니다.

머릿속 그림: 현재 건물 3개 층 안에서만 방을 추가했으므로 새 층 공사가 필요 없습니다.

\[h_{\mathrm{old}}=2\]
\[h_{19}=2\Longrightarrow h_{\mathrm{new}}=2\]

실제 시험 문제 풀이를 단계별로 연결

  1. 4(b)의 시작 L1에 어떤 key가 있어야 하나?

    4(a) 결과이므로 −∞,47,67,95가 있어야 합니다. 67을 빼고 초기 구조로 되돌아가면 누적 상태를 잃은 오답입니다.

  2. 19를 찾을 때 왜 상위 두 level의 predecessor가 head인가?

    L2와 L1 모두 head의 next가 각각 47이고 \(47>19\)47>19입니다. 오른쪽으로 가면 목표를 넘으므로 현재 head를 저장하고 아래로 내려갑니다.

  3. 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입니다.

  4. 세 난수는 각자 무엇을 뜻하나?

    0.09는 L1, 0.18은 L2 승격 성공입니다. 다음 0.39는 L3 승격 실패이며 이 실패값까지 사용한 뒤 0.06 이후는 읽지 않습니다.

  5. 왜 새 L3을 만들지 않나?

    L2에 도달한 뒤 L3 여부를 정하는 0.39가 p 이상이기 때문입니다. 19의 top level은 기존 max level 2와 같아 전체 높이도 변하지 않습니다.

전체 난수열: 사용값만 취소선

  1. 난수 0.09L1 승격 성공
  2. 난수 0.18L2 승격 성공
  3. 난수 0.39L3 승격 실패, 즉시 종료
  4. 난수 0.06미사용
  5. 난수 0.01미사용
  6. 난수 0.32미사용
  7. 난수 0.67미사용

첫 실패값까지 사용하며, 그 뒤 값은 읽지 않습니다.

난수 판정을 첫 실패까지 계산하기

  1. 난수 \(r=0.09\)r=0.09\(0.09 < 0.33\)0.09 < 0.33성공 — Level 1에 19 추가
  2. 난수 \(r=0.18\)r=0.18\(0.18 < 0.33\)0.18 < 0.33성공 — Level 2에 19 추가
  3. 난수 \(r=0.39\)r=0.39\(0.39 \ge 0.33\)0.39 ≥ 0.33실패 — 승격 종료
4(b) 결과 구조
층 2−∞1947층 1−∞19476795층 0−∞13192147666795
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결이번에 삽입한 탑(tower)

답이 맞는지 스스로 검산

  1. 최종 L0,L1,L2가 각각 오름차순이고 19가 모든 아래 level에 연속으로 존재하는지 확인합니다.
  2. 4(a)의 67 tower와 기존 47·95 tower가 사라지거나 높이가 변하지 않았는지 before/after를 대조합니다.
  3. 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을 만든다.

배점: 2점

4(c) · 18과 66 검색 경로 — 오른쪽으로 갈 수 있을 만큼 가고, 넘으면 아래로

4(b)의 최종 Skip List에서 18과 66의 검색 경로를 그린다.

이 절은 다른 소문제를 펼치지 않아도 시작 구조, 용어, 작은 예제, 실제 풀이, 검산을 모두 확인할 수 있습니다.

먼저 문제의 정체부터 파악하기

검색은 최고 Level의 head에서 시작합니다. 다음 key가 목표 이하이면 오른쪽, 다음 key가 목표보다 크거나 next가 없으면 아래로 이동합니다. 현재 key가 목표와 같으면 즉시 성공입니다.

18은 목록에 없으므로 Level 0까지 내려가 13 뒤에서 \(\text{next}=19\)next=19가 너무 큰 것을 확인한 후 nil로 내려가 실패합니다. 검색 실패도 마지막으로 비교한 위치까지 경로를 그려야 합니다.

66은 Level 2에서 19와 47을 급행으로 지나고, 67이 너무 큰 Level 1에서 내려간 뒤 Level 0의 66으로 이동해 성공합니다.

4(c) 풀이 시작 구조
층 2−∞1947층 1−∞19476795층 0−∞13192147666795
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결

이 소문제만 읽어도 풀 수 있는 초보자 강의

무엇을 배우고 왜 필요한가

Skip List의 속도는 높은 express level에서 여러 L0 node를 건너뛰고, 목표를 넘기 직전에만 아래로 내려가는 검색 경로에서 나옵니다. 성공 검색과 실패 검색을 모두 그리면 next 비교, 실제 이동, nil 종료를 구분할 수 있습니다.

  • 최고 head에서 시작해 \(\text{next}.\text{key}\le \text{target}\)next.key≤target이면 right, 아니면 down이라는 규칙을 매 단계 적용할 수 있습니다.
  • 실제 이동 edge와 ‘너무 커서 선택하지 않은 next’ 비교를 다른 표식으로 읽고 검색 경로를 재현할 수 있습니다.
  • target을 찾은 성공과 L0 아래 nil에 도달한 실패를 정확한 종료 조건으로 설명할 수 있습니다.

풀이 전에 알아둘 용어

현재 노드(current)와 다음 노드(next)

현재 노드는 지금 서 있는 노드이고 다음 노드는 같은 층의 바로 오른쪽 노드입니다. 이동하기 전에 next.key가 목표를 넘는지 비교합니다.

아주 작은 예: current=13@\(L0, \text{next}=19, \text{target}=18\)L0, next=19, target=18이면 오른쪽 이동 금지입니다.

오른쪽 이동(right move)

다음 노드가 존재하고 \(\text{next}.\text{key}\le \text{target}\)next.key≤target일 때만 현재 노드를 다음 노드로 바꿉니다. 이 규칙은 목표보다 큰 키를 지나치지 않게 합니다.

아주 작은 예: \(\text{target}=66\)target=66에서 \(19\le 66,47\le 66\)19≤66,47≤66이므로 L2에서 오른쪽입니다.

아래쪽 이동(down move)

다음 노드가 없거나 \(\text{next}.\text{key}>\text{target}\)next.key>target이면 같은 키 탑의 바로 아래 노드로 내려갑니다. 중간 층을 한 번에 건너뛰지 않습니다.

아주 작은 예: 47@L2 다음이 없으면 47@L1로 내려갑니다.

찾음(found)과 빈 포인터(nil)

\(\text{current}.\text{key}=\text{target}\)current.key=target이면 즉시 성공입니다. current.down이 nil이 되어 반복을 빠져나오면 그 키는 목록에 없습니다.

아주 작은 예: 13@\(L0.\text{down}=\text{nil}\)L0.down=nil이므로 search(18)은 실패합니다.

비유로 이해하기 · 급행을 타되 목적지를 지나치기 전에 환승하기

목적지 66을 향해 특급선에서 19와 47까지 빠르게 갑니다. 다음 급행역 67은 목적지를 지나므로 타지 않고 같은 47역의 아래 노선으로 환승합니다. 일반선에서 66을 만나면 내리고, 18처럼 두 역 사이에 표지판이 없으면 지상 아래까지 내려가 부재를 확정합니다.

  • 현재 서 있는 역current node
  • 다음 역이 목적지 이하\(\text{next}.\text{key}\le \text{target}\)next.key≤target이면 right
  • 다음 역이 목적지를 초과\(\text{next}.\text{key}>\text{target}\)next.key>target이면 down
  • 가장 아래에서도 역 없음\(\text{down}=\text{nil}\)down=nil이면 NOT FOUND

비유가 설명하지 못하는 부분: 실제 알고리즘은 뒤로 돌아가지 않고, 비교한 모든 next node로 이동하는 것도 아닙니다. 그림에서는 실선 path와 이동하지 않은 blocked comparison을 구분해야 합니다.

한 단계마다 하는 세 질문

  1. ① 현재 값이 목표와 같은가?같으면 즉시 찾음(FOUND)으로 종료합니다.
  2. ② 다음 값이 목표 이하인가?다음 노드가 있고 목표 이하이면 오른쪽으로 이동합니다.
  3. ③ 그렇지 않으면 아래로다음 값이 너무 크거나 없으면 같은 탑 아래로 갑니다.
  4. ④ 현재 노드가 nil인가?더 아래 노드가 없으면 없음(NOT FOUND)으로 종료합니다.

equality를 먼저 검사하고, 그다음 right 가능 여부를 봅니다. right가 불가능하면 down이며 L0 아래에서는 nil이 됩니다.

작은 예제로 먼저 연습 · L1=[−∞,5], L0=[−∞,2,5,8]에서 search(7)

최고 L1 head에서 시작합니다. 실제 이동과 비교했지만 선택하지 않은 \(\text{next}=8\)next=8을 구분합니다.

  1. L1 head에서 5로 right

    \(\text{next}=5\le 7\)next=5≤7이므로 목표를 넘지 않고 급행으로 이동할 수 있습니다.

    현재 상태: −∞@L1 → 5@L1

  2. 5@L1에서 down

    같은 level에 next가 없으므로 5 tower의 L0 node로 내려갑니다.

    현재 상태: 5@L1 ↓ 5@L0

  3. \(\text{next}=8\)next=8을 보고 right 거부

    \(8>7\)8>7이라 이동하면 목표를 지나치므로 5@L0에 머문 채 down을 선택합니다.

    현재 상태: 5@L0 --blocked→ 8@L0

  4. \(\text{down}=\text{nil}\)down=nil로 실패

    L0 아래 node가 없어 \(\text{current}=\text{nil}\)current=nil이 되고 search는 NOT FOUND를 반환합니다.

    현재 상태: 5@L0 ↓ nil

작은 예제의 결론: 실패는 ‘못 찾았다’는 추측이 아니라 목표가 들어갈 두 이웃 5와 8을 확인한 뒤 L0 아래로 내려가 증명됩니다.

핵심 개념을 줄글로 깊게 이해하기

0단계 · 검색(search) 규칙

current.next가 존재하고 \(\text{next}.\text{key}\le k\)next.key≤k이면 오른쪽으로 이동합니다. 그렇지 않으면 current.down으로 내려갑니다. 이 규칙 때문에 목표를 절대로 오른쪽으로 지나치지 않습니다.

\(\text{current}.\text{key}=k\)current.key==k이면 찾은 것이고, 아래로 내려갈 곳이 nil이면 목록에 없다는 뜻입니다.

머릿속 그림: 급행선을 타고 목적지를 지나치기 직전 역에서 일반선으로 환승합니다.

\[\mathrm{next.key}\le k\Longrightarrow\text{오른쪽}\]
\[\mathrm{next.key}>k\;\lor\;\mathrm{next}=\mathrm{nil}\Longrightarrow\text{아래쪽}\]

1단계 · 실패 검색: 18은 없음

2층 머리 노드(head)에서 다음 값\((\text{next})=19>18\)(next)=19>18이므로 곧바로 1층 머리 노드로 내려갑니다. 1층에서도 \(19>18\)19>18이라 0층 머리 노드로 내려갑니다.

0층에서는 다음 값 \(13\le 18\)13≤18이라 13으로 이동합니다. 이제 다음 값 \(19>18\)19>18이고 더 내려갈 층이 없으므로 18은 없습니다.

머릿속 그림: 18번 역은 13과 19 사이에 있어야 하는데 그 자리가 바로 19로 이어지므로 존재하지 않습니다.

\[(-\infty)_{2}\downarrow(-\infty)_{1}\downarrow(-\infty)_{0}\rightarrow13_{0},\qquad 19_{0}>18\Longrightarrow\text{실패}\]

2단계 · 성공 검색: 66을 찾음

2층에서 \(19\le 66,\)19≤66,이어서 \(47\le 66\)47≤66이므로 오른쪽으로 두 번 갑니다. 다음 노드가 없으므로 1층의 47로 내려갑니다.

1층에서 다음 값 \(67>66\)67>66이므로 0층의 47로 내려갑니다. 0층에서 다음 값 \(66\le 66\)66≤66이므로 66으로 이동하고 등호를 확인해 성공합니다.

머릿속 그림: 특급으로 47까지 간 뒤 67을 넘지 않도록 일반선으로 환승해 66에서 내립니다.

\[(-\infty)_{2}\rightarrow19_{2}\rightarrow47_{2}\downarrow47_{1}\downarrow47_{0}\rightarrow66_{0},\qquad 66=66\Longrightarrow\text{성공}\]

3단계 · 경로 길이와 기대 검색시간

답안의 화살표는 실제 현재 노드(current) 이동만 그리되, 왜 방향을 바꿨는지 다음 키(next key) 비교를 옆에 적으면 부분점수를 지키기 쉽습니다.

스킵 리스트는 높은 층에서 여러 0층 노드를 건너뛰므로 평균 검색 시간이 로그입니다. 다만 한 번의 구체적 구조에서는 경로 길이가 난수로 만들어진 탑 배치에 좌우됩니다.

머릿속 그림: 지도에 실제 이동선과 환승 이유를 함께 표시하면 채점자가 사고 과정을 볼 수 있습니다.

\[\mathbb{E}[T_{\text{검색}}(n)]=\Theta\!\left(\log_{1/p}n\right)\]

실제 시험 문제 풀이를 단계별로 연결

  1. search(18)은 L2에서 왜 바로 내려가나?

    head의 \(\text{next}=19\)next=19가 18보다 큽니다. 오른쪽으로 가면 목표를 넘으므로 −∞@L2에서 −∞@L1로 내려갑니다.

  2. L0에서는 왜 13까지 오른쪽으로 가나?

    \(\text{next}=13\le 18\)next=13≤18이라 안전합니다. 그 다음 \(\text{next}=19\)next=19는 18보다 커서 이동하지 않고 13@L0에서 아래를 선택합니다.

  3. search(18)의 실패를 무엇으로 확정하나?

    13과 19 사이에 18 node가 없고 13@\(L0.\text{down}=\text{nil}\)L0.down=nil이라 더 탐색할 level이 없습니다. 따라서 \(\text{current}=\text{nil}\)current=nil로 종료해 NOT FOUND입니다.

  4. search(66)은 L2에서 어디까지 가나?

    \(19\le 66,47\le 66\)19≤66,47≤66이라 −∞→\(19\to 47\)19→47로 이동합니다. L2에 next가 없으므로 47 tower를 L1으로 내려갑니다.

  5. 왜 L1의 67로 가지 않나?

    \(67>66\)67>66이라 목표를 지나치므로 blocked comparison으로만 표시합니다. 47@L1에서 47@L0로 내려간 뒤 \(\text{next}=66\)next=66으로 이동해 FOUND입니다.

검색 경로를 한 칸씩 실제로 따라가기

검색(search(18)) · 없음(NOT FOUND)

−∞@L2 ↓ −∞@L1 ↓ −∞@L0 → 13@L0 ↓ nil

19가 18보다 커서 상위 두 Level에서 즉시 내려가고, L0에서 13 다음 19가 너무 커 실패합니다.

검색(search(18))의 실제 이동과 막힌 비교
층 2−∞1947층 1−∞19476795층 0−∞1319214766679519>18 · 이동 안 함19>18 · 이동 안 함nil · 없음19>18 · 이동 안 함
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결실제 검색 이동비교했지만 이동하지 않은 노드

검색(search(66)) · 찾음(FOUND)

−∞@L2 → 19@L2 → 47@L2 ↓ 47@L1 ↓ 47@L0 → 66@L0

L2에서 47까지 이동하고 L1의 next 67을 넘지 않도록 내려가 L0에서 66을 찾습니다.

검색(search(66))의 실제 이동과 막힌 비교
층 2−∞1947층 1−∞19476795층 0−∞1319214766679567>66 · 이동 안 함
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결실제 검색 이동비교했지만 이동하지 않은 노드
4(c) 결과 구조
층 2−∞1947층 1−∞19476795층 0−∞13192147666795
다음/이전(next/prev) 양방향 포인터아래/위(down/up) 탑 연결

답이 맞는지 스스로 검산

  1. 경로의 첫 node가 최고 level의 −∞이고 모든 right edge는 도착 \(\text{key}\le \text{target}\)key≤target인지 확인합니다.
  2. 모든 down edge가 같은 key의 바로 아래 level로 이어지며 L2에서 L0로 중간 node를 건너뛰지 않는지 확인합니다.
  3. 18은 13 다음 19가 blocked이고 \(\text{down}=\text{nil}\)down=nil로 끝나며, 66은 \(\text{current}.\text{key}=66\)current.key==66에서 즉시 끝나는지 확인합니다.
  4. overlay의 실선 화살표는 실제 이동, 빨간 점선은 비교했지만 이동하지 않은 next임을 구분합니다.

30초 자가점검

search(20)은 최종 구조에서 L2의 19 뒤 어디로 가나?

힌트: L2의 다음 47과 target 20을 비교하세요.

정답: \(47>20\)47>20이라 19@L2에서 19@L1로 내려가고, 다시 L0로 내려가 \(\text{next}=21>20\)next=21>20을 확인한 뒤 nil로 실패합니다.

next.key가 target과 같으면 right인가 down인가?

힌트: 조건은 <가 아니라 ≤입니다.

정답: right로 그 node에 이동하고 다음 loop의 equality 검사에서 FOUND를 반환합니다.

47@L2에서 바로 47@L0로 내려가도 경로 답이 맞나?

힌트: down pointer는 어느 level을 가리키는지 확인하세요.

정답: 아닙니다. down은 바로 아래 47@L1을 가리키므로 경로에 L1 node를 포함해야 합니다.

시험 답안 템플릿

18 검색: −∞₂↓−∞₁↓−∞₀→\(13₀\)13₀뒤 \(19>18\)19>18이므로 없음(NOT FOUND). 66 검색: −∞₂→19₂→47₂↓47₁↓\(47₀\to 66₀\)47₀→66₀에서 찾음(FOUND). 다음 키가 목표보다 크면 오른쪽으로 넘지 않고 아래로 간다.

초보자가 자주 틀리는 지점

  • 검색을 Level 0에서 시작한다.
  • next.key가 목표보다 큰데도 오른쪽으로 이동한다.
  • 18이 없다는 결론만 쓰고 실패 경로를 그리지 않는다.
  • L2의 47에서 L0로 한 번에 내려가 중간 tower node를 생략한다.
  • 66 대신 상위 Level의 67로 이동했다가 되돌아온다. Skip List search는 뒤로 가지 않습니다.
  • 4(b) 이전 구조에서 검색해 19·67 tower를 누락한다.

근거와 정확성 범위

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