230317

1. 그래프

이진 트리 - DFS

깊이 우선 탐색 : 리프노드까지 아래로 내려가면서 탐색한다. 리프에 도달하면 부모에게 돌아간다. 그후 다시 자식노드로 내려간다.

전위 순회

: 노드 방문 => 왼쪽 자식 => 오른쪽 자식 순서로 우선 탐색을 진행한다.

중위 순회

: 왼쪽 자식 => 노드방문 => 오른쪽 자식

후위 순회

: 왼쪽 자식 => 오른쪽 자식 => 돌아와 노드 방문

이진 트리 - BFS

너비 우선 탐색 : 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가 한 레벨에서 탐색이 끝나면 다음 레벨로 내려간다.


2. 그래프

정점과 간선을 이용해 연결되어 있는 원소 사이 다대다 관계 표현한 자료구조

  • 차수 : 정점에 연결되어 있는 간선의 수
  • 경로 : 정점 A에서 B까지 간선으로 연결된 정점을 순서대로 나열

방향 그래프 vs 무방향 그래프

연결 그래프 vs 비연결 그래프

가중치 그래프

엣지 리스트

  • 2차원 배열을 이용, 에지 중심으로 그래프 표현

  • 코딩테스트에서 입력으로 주어지는 경우가 많음

인접 행렬

  • 2차원 배열을 이용, 노드 중심으로 그래프 표현

  • 노드에 비해 간선이 작은 경우 메모리/탐색 효율이 낮음

인접 리스트

  • ArrayList를 배열에 넣는 방법, 노드 중심으로 그래프를 표현

  • 공간 효율이 좋고 각 노드에 연결되어 있는 엣지를 탐색하는데 빠름

  • 실제 코딩테스트에서 가장 많이 선호되는 그래프 표현 방식

그래프 DFS

  • 백트래킹을 구현할 때 주로 사용되는 알고리즘이다.

그래프 BFS

시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

  • 주로 최솟값을 구할 때 사용되는 알고리즘이다.

profile
선한 영향력을 만드는 개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN