홍라이프 계산기그래프 메모리 계산기 쉽게 이해하기 — 개념과 원리
그래프는 가능한 모든 간선을 V × V 격자로 표시하는 인접 행렬이나, 각 정점이 실제 이웃만 저장하는 인접 리스트로 저장할 수 있습니다. 이 계산기는 두 방식의 메모리와 그래프의 밀도를 추정해, 큰 네트워크나 도로망, 소셜 그래프를 불러오기 전에 어떤 표현을 쓸지 정하도록 돕습니다.
계산 방법
- 인접 행렬: 칸당 1비트로 보고 V²비트 ÷ 8 ÷ 10⁹ GB입니다.
- 인접 리스트: (V + 2E) × 항목당 바이트 ÷ 10⁶ MB입니다. 무방향 간선은 양 끝 정점의 리스트에 한 번씩 들어가 2E개가 되고, 정점마다 위치 항목이 하나씩 더해집니다.
- 밀도: E ÷ (V(V − 1) ÷ 2) × 100%로, 가능한 무방향 간선 중 실제로 있는 비율입니다.
원리
행렬은 연결 여부와 상관없이 모든 정점 쌍에 칸을 하나씩 두므로 크기가 V²에 비례하고 E와는 무관합니다. 인접 리스트는 V + E에 비례합니다. 여기서 계산하는 압축 형태는 CSR(compressed sparse row)과 비슷해, 정점마다 시작 위치를 담은 배열과 이웃을 모은 배열 하나로 이루어집니다. 현실의 그래프는 대부분 희소해서 가능한 이웃이 V − 1개인데도 실제 이웃은 몇 개에서 수천 개 정도이므로, 리스트가 훨씬 작습니다. 행렬은 그래프가 조밀하거나 두 정점의 연결 여부를 상수 시간에 확인해야 할 때 유리합니다.
예제 풀이
- 입력값: V = 100,000, E = 1,000,000, 항목당 4바이트입니다.
- 행렬: 100,000² = 10¹⁰비트 ÷ 8 = 1.25 × 10⁹바이트 = 1.25 GB입니다.
- 리스트: (100,000 + 2 × 1,000,000) × 4 = 8,400,000바이트 = 8.4 MB입니다.
- 밀도: 1,000,000 ÷ 4,999,950,000 ≈ 0.02%입니다.
행렬이 칸당 1비트만 써도 리스트가 약 150배 작습니다.
| 정점 수 | 인접 행렬 (GB, 1비트) |
|---|---|
| 25,000 | 0.078125 |
| 50,000 | 0.3125 |
| 75,000 | 0.703125 |
| 100,000 | 1.25 |
| 125,000 | 1.953125 |
| 150,000 | 2.8125 |
| 200,000 | 5 |
결과 해석
밀도가 0%에 가까우면 희소 그래프이므로 리스트를 씁니다. 항목당 4바이트일 때 2E × 32 ≈ V², 즉 밀도 약 3%에서 두 방식의 크기가 비슷해지고, 그보다 조밀해질수록 행렬이 경쟁력을 갖습니다. 평균 차수 2E ÷ V(이 예에서는 20)도 빠르게 판단하는 지표입니다.
흔한 실수
- 방향 그래프에 V + 2E를 쓰는 경우입니다. 방향 그래프는 간선을 한 번만 저장하므로 V + E입니다.
- 간선 가중치를 빠뜨리는 경우입니다. 항목마다 값이 하나 더 필요합니다.
- 정점이 약 42억 9천만 개를 넘는데 4바이트 ID를 쓰는 경우입니다.
자주 묻는 질문
인접 행렬은 언제 쓰나요?
정점이 적거나 조밀한 그래프, 또는 플로이드-워셜처럼 어차피 모든 쌍을 보는 알고리즘에 씁니다.
단위는 십진 단위인가요?
네. 1 GB = 10⁹바이트, 1 MB = 10⁶바이트로 계산합니다.
방향 그래프에서 들어오는 간선도 저장하려면요?
역방향 그래프용 CSR을 하나 더 두며, 리스트 메모리가 두 배가 됩니다.
출처: T. H. Cormen 외, Introduction to Algorithms, MIT Press · R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley