이것이 코딩 테스트다1 [ Chapter.05 ] DFS / BFS 이론 그래프의 기본 구조 DFS / BFS 알고리즘에 대한 설명에 앞서, 그래프의 기본 구조 두 가지에 대해 살펴보겠습니다. 01) 인접 행렬 인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식 입니다. 연결 되어 있지 않은 노드끼리는 무한이라고 작성합니다 (INF) 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 낭비됩니다. 02) 인접 리스트 인접 리스트는 각각의 노드에 연결된 노드의 정보를 차례대로 연결하여 저장합니다. 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용합니다. 연결된 데이터를 하나씩 확인해야 하기 때문에 정보를 얻는 속도가 느립니다. DFS Depth-First Search 깊이 우선 탐색이라고 부릅니다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다... 2022. 7. 27. 이전 1 다음