목록깊이 우선 탐색 (2)
Seung's Learning Record
DFS(Depth First Search) 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘이다. 넓게 탐색하는 것이 아닌 깊게 탐색하는 방법이다. 각각의 좌표가 시작 좌표에서 떨어진 거리를 알 수 있었던 bfs와 달리 dfs는 거리 측정이 힘들다. 그래서 배열에서 탐색을 하는 문제에선 주로 BFS를 사용하여 문제를 푼다. 그렇다고 DFS가 아예 안쓰이는 것은 아니니 잘 이해하고 넘어가는게 좋다. DFS 구현 이론 큐를 사용하는 BFS와 달리 DFS는 스택을 사용하여 구현한다. BFS에서 사용한 예시인 파란칸 찾기 문제를 예시로 대략적인 플로우를 살펴보자. 시작 좌표 방문 표시 후, 스택에 push 스택의 top값을 pop하고 해당 좌표에 접해있는 상,하,좌,우 좌표를 확인 인접 좌표..
브루트 포스? 브루트 포스(brute force)의 사전적 의미는 '무식한 힘'이다. 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다.'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 복잡한 알고리즘없이 빠르고 쉽게 구현이 가능하다는 장점이 있지만, 알고리즘의 실행시간이 오래걸리며 메모리 효율성이 떨어진다는 단점이 있다. 종류 선형 구조 : 순차탐색 비선형 구조 : 백트래킹, DFS, BFS 선형 구조 - 순차탐색 순차 탐색(Sequential Search)는 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로..