기어가더라도 제대로

정의 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. DFS, BFS 정말 많이 나오는데 코테를 풀 때는 꼭알고 있어야하는 개념이다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 좌우한다. 어떻게 작성할 것인가? 우선, 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머..

BFS Breadth - First - Search 너비 우선 탐색이다. 최단 거리를 구하는 알고리즘에서 사용이 된다. DFS Depth - First - Search 깊이 우선 탐색 마찬 가지로 최단 거리를 구하는 알고리즘에서 사용된다. 사용처 최단 거리를 구하는 알고리즘 그림판 알고리즘 D에서 G로 가는 최단거리는? 그래프 탐색 알고리즘 너비 우선 탐색 깊이 우선 탐색 너비 우선 탐색 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 정점, A,B,C 등 기준점 큐를 이용해 탐색한 정보를 관리 D를 먼저 탐색 -> D를 엔큐 이어서 같은 거리에 있는 E, A 등을 탐색 -> E, A를 엔큐 D를 디큐, E를 디큐하고 E에서 갈 수 있는 정점이 없으므로 엔큐는 하지 않는다. A에서 갈 수 있는 B와 C를..