🗒️ 책 & 강의 정리/🏗️ 누구나 자료구조와 알고리즘
18장 그래프로 뭐든지 연결하기
친구를 맺어주는 소셜 네트워크를 만든다고 하자. 친구 관계는 상호적이다. 이런 데이터를 가장 잘 조직하는 방법은 무엇일까? 한 가지, 매우 간단한 접근 방식은 2차원 배열로 친구 관계 리스트를 저장하는 것이다. 그러나 2차원 배열로는 A의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록을 전부 확인해야 하므로 O(N)이 필요하다. 그래프를 사용하면 A의 친구를 O(1)만에 빠르게 찾을 수 있다. 1. 그래프 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 1.1 그래프 대 트리 그래프는 앞서 다뤘던 트리와 비슷하다. 사실 트리도 그래프의 한 종류다. 모든 트리는 그래프이지만, 모든 그래프가 트리는 아니다. 트리로 규정되는 그래프는 사이클이 없어야 하며, 모든 ..
