[Algorithm] 탐색 알고리즘 DFS/BFS

DFS (Depth-First-Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다. DFS의 장점 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다. DFS의 단점 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다. DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문이다. BFS (Breadth-First-Search) 너비 우선 탐색이라고도 부르며 가까운 노드부터 탐색하는 알..

[Algorithm] 알고리즘의 복잡도와 Big-O 란?

알고리즘이란 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들의 집합을 의미한다. 가는 루트는 다양하며 여러가지 상황에 따른 알고리즘은 모두 다르다. 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다. 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘을 수행할 때 연산이 몇번 이루어지는 지를 표기 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 빅오 표기법(Big O Notation) 복잡도를 표현할때에는 빅오 표기법을 ..