14강 / 20강

그래프 — 관계를 그리는 방법

함께 산 상품 · 카테고리 · 배송 경로는 모두 같은 모양이다

쇼핑몰을 운영하다 보면 "연결"에 관한 질문을 계속 받게 됩니다.

이 상품을 산 사람들이 같이 산 상품은?
이 카테고리 아래에 어떤 카테고리들이 있지?
서울 창고에서 제주까지 가장 싼 경로는?
이 계정과 연결된 의심 계정들은?

이 모든 질문이 같은 자료 구조 위에서 풀립니다. 그래프(graph)예요.

고등학생관계를 그리는 방법

그래프는 수학의 그래프(함수 그림)가 아닙니다.

점과 선으로 관계를 나타낸 것

부품이 딱 둘

부품	무엇	쇼핑몰에서
정점 (노드)	점	상품 · 고객 · 도시
간선 (엣지)	선	함께 구매 · 친구 · 도로

둘뿐인데 세상 거의 모든 관계를 그린다

같은 모양이 여기저기 있습니다

무엇	정점	간선
SNS	사람	친구 관계
지하철	역	노선
웹	페이지	링크
함께 구매	상품	같이 산 적 있음

문제가 달라 보여도 그래프면 같은 도구로 푼다

이게 그래프를 배우는 이유입니다

한 번 배우면 여러 문제에 씁니다.

"이 상품과 비슷한 것" → 그래프 탐색
"가장 빠른 배송 경로" → 최단 경로
"친구의 친구" → 2단계 이웃

추천 · 경로 · 관계 — 전부 그래프 문제다

고등학생그래프의 부품은 딱 둘

note 를 조금 더 봅시다. 방향과 가중치 이야기예요.

방향이 있나 없나

	무방향	방향
예	친구 (서로)	팔로우 (한쪽만)
쇼핑몰	함께 구매	"이거 산 사람이 저것도"

A→B 라고 B→A 인 건 아니다

가중치가 있나 없나

	없음	있음
뜻	연결됐나 아닌가	얼마나 연결됐나
예	친구인가	몇 번 함께 샀나 · 거리 몇 km

가중치가 있으면 "가장 가까운" 을 물을 수 있다

담는 방법 두 가지

	인접 행렬	인접 리스트
모양	n × n 표	점마다 이웃 목록
공간	n²	간선 수만큼
언제	빽빽할 때	대부분의 경우

실제 그래프는 드문드문하다 — 그래서 리스트

상품이 10,000개인데 한 상품이 10개쯤과 연결됐다면?

방법	저장 칸
행렬	1억 칸 (거의 다 0)
리스트	10만 칸

1,000배 차이 — 그래서 실무에서는 리스트

그래프를 코드로 담는 두 가지 방법

① 인접 리스트 — 각 점마다 "내가 이어진 점들"의 목록. 실무에서 거의 항상 이걸 씁니다.

② 인접 행렬 — n×n 표에 이어졌으면 1, 아니면 0. 간단하지만 점이 3만 개면 9억 칸이 필요합니다.

같은 관계를 두 가지로 표현했습니다. 어느 쪽이 더 효율적일까요?

Python 브라우저에서 실행

# ① 인접 리스트 — 함께 구매 관계
함께구매 = {
    "이어폰":   ["케이스", "충전기", "필름"],
    "케이스":   ["이어폰", "필름"],
    "충전기":   ["이어폰", "케이블"],
    "필름":     ["이어폰", "케이스"],
    "케이블":   ["충전기"],
    "마우스":   ["키보드"],
    "키보드":   ["마우스"],
}

for 상품, 이웃 in 함께구매.items():
    print(f"  {상품:<6} ── {', '.join(이웃)}")

print()
print("이어폰과 함께 산 상품:", 함께구매["이어폰"])
print("이어폰의 연결 개수(차수):", len(함께구매["이어폰"]))

# ② 인접 행렬 — 같은 정보를 표로
상품들 = list(함께구매)
print()
print("인접 행렬")
print("        " + " ".join(f"{s[:2]:>3}" for s in 상품들))
for a in 상품들:
    행 = [1 if b in 함께구매[a] else 0 for b in 상품들]
    print(f"  {a:<6} " + " ".join(f"{v:>3}" for v in 행))

행렬 vs 리스트 — 실무에서는 리스트

	인접 리스트	인접 행렬
메모리	`O(정점+간선)` ✅	`O(정점²)` 💀
"A의 이웃 전부"	즉시 ✅	한 줄 n칸 훑기
"A와 B가 이어졌나"	이웃 목록 훑기	즉시 ✅

쇼핑몰 데이터는 희소(sparse)합니다 — 상품 3만 개가 있어도 한 상품이 이어진 상품은 보통 10개 남짓이에요. 그래서 인접 리스트가 압도적으로 유리합니다.

고등학생행렬 vs 리스트 — 실무에서는 리스트

note 가 그 이유를 짚습니다. 왜 대부분 리스트인지요.

현실의 관계는 드문드문하다

숫자로 보면

SNS	가능한 관계	실제 관계
사용자 1,000만	50조	사용자당 수백

가능한 것의 0.00001% 도 안 됩니다. 그런데 행렬은 가능한 전부를 위한 칸을 만들어요.

쓰지도 않을 칸에 메모리를 다 쓴다

비유 — 전화번호부

방식	어떻게
행렬	모든 사람 × 모든 사람 표를 만들고 "통화했나" 를 O/X 로 적는다
리스트	사람마다 통화한 사람 목록만 적는다

대부분이 X 인 표는 만들 이유가 없다

그럼 행렬은 언제 쓰나

정점이 적다 (수십 개)
간선이 빽빽하다
"A 와 B 가 연결됐나" 를 아주 자주 묻는다 (행렬은 O(1))

묻는 방식이 담는 방식을 정한다

9강의 리스트 vs 집합 과 같은 판단이에요 — 무엇을 자주 하느냐 로 고릅니다.

🎮 관계망 편집기

점을 클릭해 선을 잇거나 끊어 보세요. 인접 리스트와 인접 행렬이 동시에 갱신됩니다. 점의 개수를 늘리면 행렬이 얼마나 빨리 커지는지도 보여 줍니다.

쇼핑몰의 그래프들

그래프	정점	간선	쓰임새
함께 구매	상품	같은 주문에 담김 (가중치=횟수)	추천 (15강)
카테고리	카테고리	상위→하위 (트리)	메뉴 전개
배송망	창고·집하지	운송 가능 (가중치=비용)	최저 비용 경로
계정 관계	계정	같은 카드·IP·주소 사용	부정거래 탐지 (18강)
서비스 의존	서버·서비스	A가 B를 호출	장애 영향 범위 파악

고등학생트리는 그래프의 특별한 경우

note 가 트리를 소개합니다. 그래프의 한 종류예요.

트리 = 순환이 없는 연결 그래프

쉽게 말하면

돌아오는 길이 없는 그래프입니다. 어디서 출발하든 제자리로 안 돌아옵니다.

예	왜 트리인가
카테고리	대분류 → 중분류 → 소분류
폴더 구조	폴더 안에 폴더
회사 조직도	상사는 하나
가계도	부모가 있다

계층이 있으면 대개 트리다

트리의 좋은 점

길이 하나뿐이다 — A 에서 B 로 가는 길이 유일
순환 걱정이 없다 — 무한 반복이 안 생긴다
간선 수가 정점 − 1 로 정해져 있다

단순해서 다루기 쉽다

그래서 순환을 조심해야 합니다

다음 note 가 그 이야기입니다. 순환이 있는 그래프를 훑다가 무한 반복에 빠지는 문제요.

상황	무슨 일
A → B → C → A	계속 돌 수 있다
방문 표시 없이 탐색	영원히 안 끝난다

1강의 조건 — 끝나야 알고리즘이다

해결은 단순합니다 — 가 본 곳을 기록해 두면 돼요. 15강에서 그 방법을 씁니다.

재귀로 트리를 훑는 기본형입니다. 15강에서 본격적으로 다룹니다.

Python 브라우저에서 실행

# 카테고리 트리 — 그래프의 특별한 형태
카테고리 = {
    "전자기기": ["음향기기", "주변기기"],
    "음향기기": ["이어폰", "스피커"],
    "주변기기": ["마우스", "키보드"],
    "이어폰": [], "스피커": [], "마우스": [], "키보드": [],
}

def 그리기(노드, 깊이=0):
    print("   " * 깊이 + ("└ " if 깊이 else "") + 노드)
    for 자식 in 카테고리[노드]:
        그리기(자식, 깊이 + 1)

그리기("전자기기")

print()
# 잎(하위 카테고리가 없는 것)만 모으기 — 실제 상품이 걸리는 곳
잎 = [k for k, v in 카테고리.items() if not v]
print("실제 상품이 등록되는 최하위 카테고리:", 잎)

🤔 확인 문제

상품 30,000개의 '함께 구매' 관계를 인접 행렬로 저장하면 필요한 칸 수는?

🤔 확인 문제

카테고리 구조처럼 순환이 없고 부모가 하나인 그래프를 무엇이라 부를까요?

🤔 확인 문제

그래프를 훑을 때 방문한 곳을 기록해야 하는 이유는?

해설 A→B→C→A 같은 순환이 있으면 영원히 돕니다. visited 집합으로 막는 것이 그래프 탐색의 기본이에요.