Day 07 · 인접 리스트와 희소성

A SMALL DETOUR

이번 회차, 내 속도로.

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

난이도·관심 주제 고르기

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

더 살펴볼 주제 1~2개 선택CSR·행 포인터추가 03 · 새 수업 · 7회차에서 인접 리스트가 칸을 아낀다는 것을 본 뒤, 그 리스트를 메모리에 실제로 어떻게 늘어놓는지 확인합니다.행렬 거듭제곱·걸음 수추가 04 · 새 수업 · 6회차의 인접 행렬을 저장 형식이 아니라 계산 도구로 써 보는 심화 수업입니다.인접 행렬DAY 6 · 인접 행렬의 행과 열을 읽으면 차수와 방향을 표에서 바로 계산할 수 있습니다.차수 분포·허브DAY 8 · 악수 정리와 차수 분포로 그래프 전체의 모양과 허브의 존재를 확인합니다.경로·사이클·연결 요소DAY 9 · 경로·사이클·다리를 알아야 탐색과 커뮤니티 회차에서 연결 구조를 해석할 수 있습니다.슈퍼노드·팬아웃DAY 44 · 차수가 아주 큰 허브가 그래프 DB 탐색을 폭발시키는 슈퍼노드 문제로 이어져, 차수 분포가 실무에서 왜 중요한지 봅니다.

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

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

출발 · DAY 7인접 리스트·희소성
1. 관심 주제CSR·행 포인터추가 03 · 새 추가 수업
복귀 · DAY 7원래 회차 이어가기

CSR·행 포인터 · 7회차에서 인접 리스트가 칸을 아낀다는 것을 본 뒤, 그 리스트를 메모리에 실제로 어떻게 늘어놓는지 확인합니다.

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

복귀: DAY 7 → 본과정 다음 회차: DAY 8

01 / UNDERSTAND

핵심 개념

인접 리스트(adjacency list)는 노드마다 이웃 목록만 적습니다. 동아리 네트워크라면 ‘민수: 지아, 서준’, ‘하린: 지아, 서준, 도윤’처럼 8줄이면 끝납니다. 행렬이 ‘이어지지 않았다’는 사실까지 0으로 적는 반면, 리스트는 있는 연결만 적습니다. 한 노드의 이웃을 차례로 훑는 탐색(11·12회차)에 잘 맞습니다.

필요한 칸을 비교해 봅니다. 행렬은 언제나 N²칸입니다. 리스트는 노드 머리 N개에 이웃 항목을 더해 방향 그래프에서는 N+E개, 무방향 그래프에서는 엣지마다 양쪽 목록에 한 번씩 적으므로 N+2E개입니다. 동아리 네트워크는 행렬 64칸 대 리스트 8+22=30항목입니다. 노드가 늘수록 N²은 N+E보다 훨씬 빨리 커집니다.

가능한 엣지 중 실제로 있는 엣지의 비율을 밀도(density)라고 합니다. 무방향이면 E÷(N(N−1)÷2)입니다. 동아리 네트워크는 11÷28≈0.39로 꽤 촘촘하지만, 큰 실제 그래프는 대부분 밀도가 매우 낮은 희소(sparse) 그래프입니다. 사용자가 1억 명인 서비스에서 한 사람의 친구가 수천 명이라도 가능한 상대의 극히 일부입니다.

리스트에도 대가가 있습니다. ‘민수와 보라가 이어졌는가’를 확인하려면 민수의 목록을 훑어야 하므로 행렬처럼 칸 하나로 바로 답하지 못합니다. 이웃이 아주 많은 노드는 목록을 정렬하거나 해시 구조를 함께 두어 찾는 시간을 줄입니다.

인접 리스트는 있는 연결만 적어 N+E에 비례하는 공간을 쓰므로, 대부분이 0인 희소 그래프에 알맞습니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

동아리 네트워크의 인접 리스트는 8줄이고, 이웃 항목은 2+3+3+3+3+3+3+2=22개입니다. 엣지 11개가 양쪽 목록에 한 번씩 적혔습니다.

행렬로 적으면 8×8=64칸 중 1이 22칸, 0이 42칸입니다. 리스트는 머리 8개와 항목 22개를 합해 30개로 절반이 안 됩니다.

노드 1,000개, 평균 진출 차수 5인 방향 그래프라면 행렬은 1,000,000칸, 리스트는 1,000+5,000=6,000항목으로 약 167분의 1입니다. 행렬에서 1인 칸의 비율은 5,000÷1,000,000=0.5%입니다.

03 / EXPLORE

직접 실험해 보기

상단의 동아리 네트워크 인접 리스트에서 항목 수를 먼저 세어 본 뒤, N과 평균 차수 k 슬라이더를 움직이며 행렬 칸 수 N²과 리스트 항목 수 N+N·k의 비율, 채워진 칸 비율이 어떻게 변하는지 확인하세요.

LIVE EXPERIMENT · ADJACENCY LIST

행렬 칸 수와 리스트 항목 수 비교하기

동아리 네트워크의 실제 인접 리스트 (노드 8 · 항목 22)

민수 → 서준, 지아
지아 → 민수, 서준, 하린
서준 → 민수, 지아, 하린
하린 → 도윤, 서준, 지아
도윤 → 유나, 태오, 하린
유나 → 도윤, 보라, 태오
태오 → 도윤, 보라, 유나
보라 → 유나, 태오

무방향 엣지 하나는 양쪽 목록에 한 번씩 들어가 8 + 2×11 = 30칸. 같은 그래프의 행렬은 8² = 64칸이고 그중 22칸만 1입니다.

리스트가 2.1배 작음지금 값은 동아리 네트워크(N=8, 평균 차수 2.75)와 같습니다. N을 1,000으로 늘려 보세요.

노드 수 N8평균 차수 k2.75

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

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

문제 1

노드 100개, 무방향 엣지 300개인 그래프가 있습니다. 인접 행렬의 칸 수와 1인 칸 수, 인접 리스트의 항목 수(노드 머리 포함)를 구하세요.

힌트 보기

무방향 엣지 하나는 행렬에서 두 칸, 리스트에서 두 항목을 차지합니다.

풀이와 비교하기

행렬은 100²=10,000칸이고 1인 칸은 300×2=600칸(6%)입니다. 리스트는 머리 100개와 항목 600개를 합해 700개입니다.

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

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

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

인접 리스트와 희소성