🚀 The Algorithm Mastery Series ( part 4 )

Context

그래프는 단순한 데이터 리스트가 아니라 항목 간 관계를 나타내는 구조로, 소셜 네트워크, 내비게이션, 추천 시스템 등 2026년의 현대적 시스템 전반을 지탱하고 있다. 실제 그래프 문제 해결을 위해서는 올바른 자료구조 선택과 적절한 순회 알고리즘 이해가 필수적이다.

Technical Solution

• 그래프 표현 방식 선택: Adjacency List(공간 O(V + E), 엣지 확인 O(degree))를 대규모 실제 그래프(소셜 네트워크, 로드 네트워크)에, Adjacency Matrix(공간 O(V²), 엣지 확인 O(1))를 소규모 완전 그래프에 적용
• 친구 추천 알고리즘 설계: BFS를 사용해 사용자를 기준으로 레벨별 탐색(Level 0: 사용자 본인, Level 1: 직접 친구, Level 2: 친구의 친구)을 구현
• 점수 메커니즘 도입: 추천 대상 사용자의 상호 친구 수를 계산해 점수화, 상호 친구가 많을수록 더 나은 제안으로 평가
• C++ 구현: unordered_map을 이용한 Adjacency List 기반 SocialNetwork 클래스 작성으로 userId와 친구 리스트 매핑
• 성능 최적화: BFS 조기 종료(전체 그래프 탐색이 아닌 필요한 깊이까지만 탐색) 가능성 언급

Key Takeaway

그래프 기반 시스템 설계 시 자료구조 트레이드오프(밀집 vs 희소 그래프)를 먼저 판단하고, 해결 대상 문제의 거리/관계 패턴에 맞는 순회 알고리즘(BFS, DFS, Dijkstra)을 선택하는 것이 핵심이다. 이는 LinkedIn 규모의 500M+ 사용자 그래프에서도 100ms 이하의 응답 속도를 달성하는 기초가 된다.