보호되어 있는 글입니다.
보호되어 있는 글입니다.
보호되어 있는 글입니다.
보호되어 있는 글입니다.
[Algorithm] - Dynamic Programming 알고리즘
dp 알고리즘 더보기 참고: https://hongjw1938.tistory.com/47 DP, 즉 Dynamic Programming(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 일반적인 재귀 방식 또한 DP와 매우 유사하다. 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산될 수 있다는 것이다. 피보나치 수를 재귀로 함수를 구성하면 return f(n) = f(n-1)+ f(n-2) ⇒ f(n-1)에서 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문 한번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면? ⇒ dp O(n^2)→O(f..
[Algorithm] - BFS(Breadth-First Search)
알고리즘 문제에서 자주 다뤄지는 BFS에 대해 알아보자. BFS란? BFS는 말 그대로 너비 우선 탐색으로 깊게 탐색하는 dfs와는 달리 인접한 노드부터 넓게 탐색하는 방법이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 말한다. BFS 사용하는 경우: 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때 ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우 > DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색 > BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색 BFS 특징 1️⃣ 재귀적으로 동작 x 2️⃣ 노드 방문 여부를 반드시 검사해야한다. : 방문한 노드를 재방문할..