놀이터 기록소

BFS, DFS, 재귀함수 (feat. 백준 1697)1. 그래프여러 노드와 간선으로 이루어진 네트워크나 자료구조그래프가 주로 쓰이는 유형은 (개인 경험 상)(점화식같은) 수 많은 경우의 수 중에서 일부인 경우를 찾아야 하는 경우노드와 노드 사이의 관계(간선의 정보)를 이용하여 푸는 경우이렇게 2가지라고 생각한다.그래프는 종류에 따라 여러 그래프가 있는데 그 이론은 다른 포스트에서 설명할게요.2. DFS깊이 우선 탐색 (DFS - Depth First Search)그림과 같이 한 분기를 전부 탐색하고 다른 분기로 넘어가면서 탐색하는 알고리즘이다. DFS는 스택이나 재귀함수로 알고리즘을 구현 할 수 있다.다른 사이트에서 공부하며 찾아본 바로는 모든 노드를 찾는게 BFS보다 빠르다고 한다.3. BFS너비 우..

시간 복잡도란시간 복잡도란 알고리즘을 수행하는데 걸리는 시간을 말하며보통 다룰 변수의 크기 혹은 개수 를 n으로 두고 계산한다. 시간 복잡도를 분석 종류로는 3가지이며최악인 경우 에서의 시간, 평균적인 경우 에서의 시간, 최적의 경우 에서의 시간으로 나뉜다.여기서는 보통 최악의 경우에서의 시간을 다루며 평균적인 경우에서의 시간은 가끔 쓰인다고 한다. 시간 복잡도를 식으로 표현하는 예로는 아래처럼 하면 된다.int factorial(int n) { return n == 1 ? n : n * factorial(n - 1); }위 코드는 factorial을 재귀 함수로 구현한 코드이며 해당 함수의 시간 복잡도는 아래의 식처럼 나온다. $T(n) = T(n - 1) + c$ ($c$ 는 상수, $T(1) = c..