목록2021/12/02 (1)

Data Scientist(DS)

S532 Graph

개념 정리 1) 그래프 그래프란? 노드와 엣지(간선)으로 이루어진 자료구조. 트리와 다른 점: 계층이 존재하지 않는다. (=루트노드 x) 장점: object간 관계를 표현할 때 유용하다. 예를 들어 SNS나 운송 시스템 같은 경우 적합하다. 그래프 코드 구현 시인접행렬(Adjacency Matrix) 인접리스트 (Adjacency List) 두가지로 구현 가능하다. 인접행렬(Adjacency Matrix) 연결된 여부는 1로 (만약 가중치가 1보다 크면 1보다 큰 값으로) 연결되지 않으면 0으로 표현한다. 메모리 차지가 인접리스트보다 많다. 시간 복잡도 O(n^2) 차지. 노드간 엣지가 존재하는지 찾기 위해서 시간 복잡도가 O(1)으로 인접 리스트보다 좋다. 인접리스트 (Adjacency List) 딕셔..
AI 부트캠프/Computer Science 2021. 12. 2. 21:39
이전 Prev 1 Next 다음