muntari Log muntari Log

그래프 탐색 보통 탐색은 주어진 조건에 맞는 데이터를 찾는 것을 의미 하지만 그래프에서의 탐색은 하나의 노드를 시작점으로 연결된 노드들을 모두 찾는 것을 탐색이라고 말한다. 자료구조 안에 저장된 모든 데이터를 도는 것을 순회라고 하는데 따라서, 그래프에서의 탐색도 하나의 노드에서 연결된 모든 노드를 돌기 때문에 그래프 순회라고도 부르기도 한다. (그래프 탐색과 그래프 순회는 같은 말이다.) 그래프를 탐색하며 알 수 있는 정보 그래프를 탐색하면 그래프의 구조에 대해 의미 있는 정보들을 알아낼 수 있다. 1. 주어진 두 노드가 경로를 통해 연결되어있는지 여부 2. 주어진 두 노드 사이의 최단 경로를 알아낼 수 있다. 대표적으로 두가지 정도가 있으나 정렬 등 많은 문제에서 그래프 탐색을 사용하여 문제를 해결할..

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

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