Judaeng

첫 정점에서부터 그래프에 존재하는 모든 정점들을 한 번씩 방문하는 것을 그래프의 탐색이라고 한다. 그래프의 탐색 방법에는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 2가지 방식이 있다. 말 그대로 '깊이'를 우선시해서 탐색하는지, '너비'를 우선시해서 탐색하는지에 차이가 있다. 아래 그림을 보면서 이해해보도록 하자. DFS (Depth-First Search, 깊이 우선 탐색) 깊이 우선 탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. 간단히 재귀호출(Recurse)을 사용하여 구현하거나, 스택(Stack)을 사용하여 구현한다. 스택으로 구현할 때는 모든 노드가 중복 없이 딱 한 번씩만 담겨야 하고, 재귀로..

복잡도(Complexity) 복잡도는 알고리즘의 성능을 나타내는 척도이다. 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 속도에 해당하는 알고리즘의 수행 시간 분석 결과를 말한다. 공간 복잡도는 메모리 사용량에 대한 분석 결과를 말한다. +추가 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다. 시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다. 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(Big-Ω), 빅세타(big-Θ) 표기법 등이 있다. ✏️시..