Beeeam

BFS란? Breadth-First_Search의 약자로 너비 우선 탐색 알고리즘이다. 그래프를 탐색할 때 사용되는 알고리즘이다. DFS 알고리즘처럼 그래프를 탐색하지만 탐색하는 방법이 다르다. DFS는 깊이를 우선으로 탐색하는데 BFS는 너비를 우선으로 탐색을 진행한다. 즉, 자식 노드를 탐색하기 전에 같은 레벨의 다른 노드를 탐색한다. 그럼 언제 사용함? 최단 경로, 혹은 임의의 경로를 찾을 때 사용한다 . 특징 DFS와 비교해서 설명을 해보겠다. 먼저 사용되는 자료구조에서 첫 번째 차이점이 있다. DFS에서는 stack을 사용하지만 BFS에서는 queue를 사용한다. stack은 LIFO(Last In First Out)방식으로 요소들이 관리 되고, queue는 FIFO(First In First ..

다이나믹 프로그래밍(DP) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘이다. 중복되는 계산을 줄이기 위해서 앞에서 계산한 값을 자료구조에 저장을 하는데 이러한 점 때문에 “기억하며 풀기”라고 불리기도 한다. 그럼 DP를 왜 쓸까? DP는 재귀 함수와 많이 유사한데 재귀 함수를 사용하게 되면 위에서 언급한 것처럼 중복되는 계산이 생긴다. 피보나치 수를 예로 들자면 fibonacci(5)를 구하는 것은 재귀 함수로 해도 문제가 없다. 계산 횟수가 그렇게 많지 않기 때문이다. 하지만 fibonacci(100)을 재귀 함수로 계산하면 어떻게 될까? 많은 시간이 걸린다. 그래서 앞에서 계산했던 값들을 다른 자료구조에 저장을 해놓고 연산할 때 이..