Day 14 · 몇 단계면 닿을까

A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 14로 돌아옵니다.

난이도·관심 주제 고르기

이번 회차는 어느 속도로 볼까요?기초부터새 보충 수업부터 짚어요현재 수준으로관심 주제부터 살펴봐요한 걸음 더새 심화 수업까지 넓혀요

더 살펴볼 주제 1~2개 선택FIFO·LIFO·방문 표시추가 05 · 새 수업 · 11·12회차에서 큐와 스택의 상태 변화가 헷갈렸다면, 작은 나무 모양 그래프로 한 줄씩 따라가 봅니다.f = g + h·허용 휴리스틱추가 06 · 새 수업 · 13회차의 다익스트라를 마친 뒤, 도착점이 정해져 있을 때 확정할 노드 수를 줄이는 방법을 봅니다.BFS·큐·거리DAY 11 · 큐로 층층이 넓혀 가는 BFS가 최단 홉 거리를 주는 이유를 다시 확인합니다.DFS·스택·되돌아가기DAY 12 · 스택과 되돌아가기로 움직이는 DFS의 순서를 BFS와 비교해 두 탐색의 쓰임을 구분합니다.다익스트라·완화DAY 13 · 가중치가 있을 때 확정과 완화로 최단 경로를 찾는 과정을 손으로 따라갈 수 있습니다.*1..3·shortestPathDAY 33 · Cypher의 가변 길이 패턴과 shortestPath가 BFS의 홉 거리와 같은 질문을 쿼리로 묻는 방법임을 확인합니다.

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

출발 · DAY 14홉 거리·지름·작은 세상
1. 관심 주제FIFO·LIFO·방문 표시추가 05 · 새 추가 수업
복귀 · DAY 14원래 회차 이어가기

FIFO·LIFO·방문 표시 · 11·12회차에서 큐와 스택의 상태 변화가 헷갈렸다면, 작은 나무 모양 그래프로 한 줄씩 따라가 봅니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 14 → 본과정 다음 회차: DAY 15

01 / UNDERSTAND

핵심 개념

모든 노드 쌍의 최단 홉 거리를 구해 평균 낸 값이 평균 경로 길이(average path length)이고, 그중 가장 큰 값이 지름(diameter)입니다. 연결 그래프라면 노드마다 BFS를 한 번씩 돌려 모두 구할 수 있습니다. 동아리 네트워크의 28쌍 거리를 모두 더하면 62이므로 평균 경로 길이는 62÷28≈2.21이고, 가장 먼 쌍인 민수–보라의 거리 5가 지름입니다. 지름은 가장 먼 한 쌍만 보므로 평균보다 외곽의 노드 하나에 민감합니다.

트래버스와 밀그램(Travers & Milgram, 1969)은 네브래스카와 보스턴에서 고른 출발자 296명에게, 매사추세츠에 사는 한 사람에게 아는 사람만 거쳐 문서를 전달하게 했습니다. 목표에 도착한 사슬은 64개였고, 그 사슬의 중간 전달자는 평균 5.2명이었습니다. ‘여섯 단계’라는 말이 이런 실험에서 유명해졌지만, 출발한 사슬 대부분은 도착하지 못했다는 점도 함께 기억해야 합니다.

와츠와 스트로가츠(Watts & Strogatz, 1998)는 이웃끼리만 이어진 고리 모양 그래프에서 엣지 일부를 무작위로 먼 곳에 다시 연결하는 모형을 만들었습니다. 지름길(short cut) 몇 개만 생겨도 평균 경로 길이는 빠르게 줄었지만, 이웃끼리 서로 아는 정도인 군집 계수(21회차)는 거의 그대로였습니다. 이렇게 촘촘한 동네와 짧은 평균 거리를 함께 가진 네트워크를 작은 세상(small-world) 네트워크라 부르고, 예쁜꼬마선충의 신경망, 미국 서부 전력망, 영화배우 공동 출연 그래프에서 이 성질을 확인했습니다.

평균 경로 길이와 지름은 그래프의 넓이를 재며, 먼 곳을 잇는 지름길 몇 개만으로도 평균 거리가 크게 줄어듭니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

노드 10개가 원형으로 양옆 이웃과만 이어진 고리에서 한 노드의 거리는 1, 1, 2, 2, 3, 3, 4, 4, 5로 합이 25입니다. 평균 경로 길이는 25÷9≈2.78, 지름은 5입니다.

마주 보는 두 노드(0과 5)를 지름길로 이으면 전체 45쌍의 거리 합이 125에서 109로 줄어 평균이 약 2.42가 됩니다. 지름은 여전히 5입니다.

지름길 0–5, 2–7, 4–9 세 개를 넣으면 거리 합 89, 평균 약 1.98, 지름 3이 됩니다. 엣지를 10개에서 13개로 30% 늘렸을 뿐인데 평균 거리는 약 29% 줄었습니다.

03 / EXPLORE

직접 실험해 보기

지름길이 0개일 때 평균 경로 길이와 지름이 예제(약 2.78, 5)와 같은지 확인한 뒤, 지름길을 하나씩 3개까지 늘리며 두 값이 얼마나 줄어드는지 기록하세요.

LIVE EXPERIMENT · SMALL WORLD

지름길을 더해 평균 거리 줄이기

기준 노드 (눌러서 변경)가장 먼 노드지름길

평균 2.78홉 · 지름 5홉서로 다른 45쌍의 최단 홉 거리를 모두 BFS로 구해 평균과 최댓값(지름)을 냅니다.

지름길	평균 경로 길이	지름
0개	2.778	5
1개	2.422	5
2개	2.111	4
3개	1.978	3

링만 있으면 맞은편까지 5홉. 지름길 몇 개가 평균 거리를 크게 줄이는 것이 Watts–Strogatz 작은 세상 효과입니다.

지름길 수0개

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

노드 6개짜리 고리(0–1–2–3–4–5–0)의 평균 경로 길이와 지름을 구하세요. 그리고 0–3 지름길을 추가하면 노드 0에서 각 노드까지의 거리가 어떻게 바뀌는지 적으세요.

힌트 보기

고리에서 노드 0의 거리는 1, 2, 3, 2, 1입니다. 모든 노드가 같은 처지라는 대칭을 이용하세요.

풀이와 비교하기

한 노드의 거리 합은 1+2+3+2+1=9이므로 평균 경로 길이는 9÷5=1.8, 지름은 3입니다. 0–3을 추가하면 노드 0에서 1, 2, 3, 4, 5까지의 거리가 1, 2, 1, 2, 1(합 7)이 되어, 노드 0의 가장 먼 거리가 3에서 2로 줄어듭니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.

몇 단계면 닿을까