자료구조

[알고리즘] DFS (Depth-First Search) / C++ 구현

1. DFS란? DFS는 Depth-First Search 의 줄임말로 “깊이 우선 탐색"이라고 부른다. DFS의 가장 큰 특징은 해당 노드가 더 이상 edge를 가지지 않을 때까지 따라 가다가, leaf Node에서 Back Track 하는 방식을 사용하여 탐색한다는 것이다. 즉, 중요한 것은 더 이상 edge가 없는 Node를 만났을 때, Back Track을 수행한다는 것이다. DFS 순회는 다음과 같다. end end end end end 리스트로 구현한 DFS에서 N이 모든 Node의 개수이고, M은 Node를 모두 탐색하기 위한 Edge의 개수 일 때, 단지 Node들과 필요한 Edge를 한번씩 방문하면 되기 때문에 시간 복잡도는 BFS와 마찬가지로 다음과 같다. O(|V| + |E|) 2. ..

[알고리즘] BFS ( Breadth-First Search) / C++ 구현

1. BFS란? BFS는 Breadth-First Search 의 줄임말로 “너비 우선 탐색"이라고 부른다. BFS의 가장 큰 특징은 layer의 순서대로 탐색한다는 것이다. 즉, 탐색을 시작하는 지점인 root node에서 가까운 순서대로 탐색을 수행한다. 예시로 든 다음 트리에서 1층 레이어에 10, 2층 레이어에 4와 9, 3층 레이어에 3과 1과 2와 7, 마지막 4층 레이어에 5와 6으로 이루어져 있는 것을 볼 수 있다. BFS는 이 레이어의 층 수 대로 한 층씩 내려오면서 탐색하는 방법을 뜻한다. 결국 위 트리의 BFS 순회는 다음과 같다. layer-1 layer-2 layer-3 layer-4 Queue를 이용한 리스트로 구현한 BFS에서 N이 모든 Node의 개수이고, M은 Node를 모..

[자료구조 ] Tree(트리) 필수 개념, 트리 순회

트리란? 트리는 Node 로 이루어진 자료구조 이다. 하지만 Node로 이루어져있다고 다 트리라고 부를 수 있을까? 아니다. 트리는 그래프와 구별되며 다음과 같은 특징을 가지고 있다. 트리는 최소 연결 트리라고 불린다. 두 Node 사이에 반드시 1가지의 경로만을 가진다. (ex, A에서 F로 가는 경로는 한가지이다.) 트리는 오직 한개의 Root Node를 가진다. 트리에는 loop, circuit, self-loop가 존재하지 않는다. (사이클이 없는 방향 그래프(DAG)) 트리의 순회는 Pre-Order, Inorder, Post-order로 이루어진다. Edge는 항상 Node의 개수 - 1 의 개수이다. 이진트리(Binary Tree)에 대해서 우리가 보통 BT 라고 부르는 Binary Tree..