알고리즘

BFS 알고리즘은 너비 우선 탐색이라는 의미를 갖고 있다. 말 그대로 가장 가까운 노드부터 탐색해가면서 탐색 범위를 넓혀 나가는 개념이다. DFS는 가장 깊은 노드까지 탐색하고 되돌아가서 다른 경로를 택하는 방법을 취한 것과는 반대로 동작한다는 뜻이다. BFS는 큐를 사용해서 선입선출 (FIFO) 의 방식을 사용한다. 인접 노드를 큐에 삽입하고 먼저 들어온 노드가 먼저 큐에서 나가게 되면서 인접한 노드부터 차례대로 탐색을 할 수 있는 것이다. BFS의 동작과정은 다음과 같다. BFS 동작과정 1. 탐색을 시작하는 노드를 큐에 삽입하고 방문 처리 한다. 2. 큐에서 가장 앞에 있는 노드를 꺼내서 그 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. 3. 과정2를 더 이상 반복..

DFS (Depth-First Search)란 깊이 우선 탐색의 약자로 그래프의 탐색(traversal, 순회) 방법 중 하나이다. 이 탐색 알고리즘은 말그대로 특정한 경로로 노드를 탐색하다가 가장 깊은 곳까지 탐색하고 경로를 다시 돌아가 다른 경로로 탐색하는 방식을 보인다. 구체적인 DFS의 동작 과정은 아래와 같다. DFS의 동작과정 1. 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 인접한 노드가 있을 때 아래와 같은 경우에 나누어서 처리한다. 2-1. 인접 노드 중 방문하지 않은 노드가 존재할 때, 그 노드를 방문하고 스택에 삽입, 방문 처리한다. 2-2. 인접 노드 중 방문하지 않은 노드가 존재하지 않을 때, 스택의 최상단 노드를 꺼낸다. 3. 과정2를 더 이..

복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도에는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 시간복잡도는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타내고 공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 메모리를 얼마나 차지하는지를 나타낸다. 일반적으로 적은 시간을 소요하고, 적은 메모리를 차지하는 것이 좋은 알고리즘이라는 것은 자명한 사실이다. 복잡도를 표기하는 방법에는 여러가지 방법이 있다. 빅오(Big-O)표기법 빅오메가(Ω)표기법 빅세타(Θ)표기법 빅오(Big-O)표기법 먼저 빅오(Big-O)표기법이란 쉽게 말해 함수의 상한(upper-bound)만을 고려하는 표기법이다. 즉, 가장 빠르게 증가하는 항만을 고려하는..