Leta Learns

BFS (너비 우선 탐색) : 현재 정점과 인접한 정점들에 대해 우선적으로 탐색하는 방식 => 넓게(wide) 탐색. 큐(Queue)를 이용해서 구현. 방문한 정점에 대해 표시하지 않는 경우, 무한루프에 빠질 가능성 有 => 각 정점의 기 방문 여부 저장 (visited) 아래로 깊은 그래프에 대해 좋은 성능을 기대할 수 있다. ( -> 아래로 깊은 그래프에서 해가 중간에 있는 경우) BFS의 과정 BFS 시간 복잡도 (DFS와 동일) 시간 복잡도 (N: 노드 수, E: 에지 수) 인접 행렬로 표현된 그래프 => O(N^2) 인접 리스트로 표현된 그래프 => O(N+E) 희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리 -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프 DFS v..

• DFS (깊이 우선 탐색) 그래프 : 하나의 정점으로부터 시작, 차례대로 모든 정점들을 한 번씩 방문하는 것. DFS (Depth-First-Search, 깊이 우선 탐색) : 루트 노드 (or 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. ex) 미로 탐색 시 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 이전의 갈림길로 돌아와서 다른 방향으로 다시 탐색. => 즉, 넓게(wide) 탐색하기 전에 깊게 (deep) 탐색. 모든 노드를 방문하고자 하는 경우에 선택하는 방법. • DFS의 과정 1. 시작 노드 A 방문 (방문 표시) 2. A와 인접한 노드 차례로 방문 3. A와 인접한 노드 B의 이웃 노드들도..

1. 동적계획법 : 큰 문제를 여러 개의 작은 부분으로 분할하여 해결하는 기법. 2. DP vs. Divide & Conquer Dynamic Programming Divide & Conquer 공통점 큰 문제를 여러 개의 작은 문제로 나눠서 해결한다. 차이점 작은 문제에서 중복 O 작은 문제에서 중복 X 3. DP의 조건 1) 작은(부분) 문제들이 중복된다. -> 부분 문제 한 번만 계산한 후 그 해를 테이블에 저장. -> 그 부분 문제가 중복될 때마다 테이블에서 미리 저장해둔 해를 반환. 2) 최적 부분 구조를 가진다. -> 작은 문제의 해로부터 큰 문제의 해를 구할 수 있음. 4. How To Solve DP Top-Down / 재귀함수를 사용하는 방식 (Memoization) -> 시간복잡도 문제..

1. Greedy Algorithm : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 Greedy 알고리즘은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가며 답을 구한다. 현재 상황에서 최선이라고 생각하는 것을 선택하는 방식이므로 가장 좋은 결과가 보장되는 것은 아니다. 위 그림의 경우, 가장 최적의 해는 연두색을 따라가서 얻는 결과인 107이지만 Greedy 알고리즘을 통해 값을 구하면 노란색을 따라가서 24라는 결과값이 나온다. 따라서 greedy 알고리즘이 최적해를 보장해주지는 않는다는 것을 알 수 있다. But, 어느 정도 최적해에 근접한 값을 구할 수 있다. 2. Greedy Algorithm 예시 1260원..