muntari Log muntari Log

그래프 구현하기 그래프를 구현하는 방법은 크게 2가지로 나누어 알아보자. 1. 그래프의 노드를 구현하는 방법 - 배열 또는 동적 배열 => 파이썬의 리스트로 구현이 가능하다. - 해시 테이블 => 파이썬의 딕셔너리로 구현이 가능하다. 2. 그래프의 에지를 구현하는 방법 - 인접 행렬 - 인접 리스트 먼저, 그래프의 노드를 구현하는 방법이다. 1. 동적 배열 / 파이썬 리스트 구현 방법 그래프는 노드라는 기본 데이터 단위를 가지며 리스트의 요소로 단순 값이 아닌 노드 자체를 요소로 하는 리스트를 만드는 방법이다. 이때 노드는 특정 인덱스 값을 부여받는데, 인덱스를 이용해 리스트의 O(1)으로 효율적인 접근이 가능하며, 노드 안의 인스턴스에 대한 접근도 그만큼 효율적으로 할 수 있게 되는 것이다. class..

그래프 그래프는 연결 관계에 있는 데이터를 저장하는 자료구조이다. 그래프는 노드라는 가장 작은 단위의 데이터로 이루어져 있는데, 각 노드들의 관계가 동등한 위치에 있을 경우 그래프를 적용하여도 무방할 것 같다. 자료구조를 공부해야 하는 이유는 상황에 맞는 방식으로 데이터를 저장하고 사용하기 위해서이다. 데이터 사이에 어떤 관계가 있는지 파악하고 그에 맞는 적절한 자료구조를 사용하기 위함이다. 앞, 뒤와 같은 순서 데이터를 저장하기 위해서는 배열, 링크드 리스트 같은 선형 자료구조를 상, 하 관계와 같은 계층 데이터를 저장하기 위해서는 트리와 같은 계층 자료구조를 사용하면 된다. 그렇다면 그래프는 언제 사용하는 걸까? 그래프는 연결 관계에 있는 데이터를 저장한다고 하였는데 이는 실제로 우리 생활에서 무궁무..