백트레킹 (2) 썸네일형 리스트형 브루트포스[3]:백트레킹(backtracking) 알고리즘 중 하나인 백트레킹 설명과 문제풀이. 백트레킹(backtracking, 퇴각검샘) 백트레킹은 유망성 검사를 만족하는 경우 모든 조합의 수를 살펴보는 것이다. 유망성 검사를 만족하지 않은 경우 많은 부분 조합들을 배제할 수 있고 모든 경우의 수를 모두 찾는 것보다 훨씬 빠르고 풀이 시간이 단축된다. 구현방법은 DFS와 같은 구조이지만 유망성 점검을 하냐 안하냐로 구분된다. 어떤 노드의 유망성 점검후, 유망하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. 브루트포스는 모든 방법을 만드는 것이나, 백트레킹은 아무리 해봤자 의미가 없다 싶을 때 호출을 중단하는 것. 백트레킹 알고리즘의 설명에 관해서 매우 설명이 잘되있는 블로그가 있기 때문에 참고하면 좋을 것 같다! idea-sk.. 깊이 우선 탐색(DFS, Depth-First Search) ● 1. 깊이 우선 탐색의 개념● 2. 깊이 우선 탐색의 특징● 3. 깊이 우선 탐색의 구현그래프 탐색이란그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용한다.DFS는 버텍스의 자식들을 먼저 탐색하고, BFS는 버텍스의 형제들을 먼저 탐색한다.ex) 미로 탈출, 최단거리 탐색, 특정 지점에서 다른 점으로 갈 수 있는지 등의 문제를 해결할때 사용하는 알고리즘 1. 깊이 우선 탐색의 개념 깊이우선 탐색 (Depth First Search) : 탐색 트리의 특정 노드를 방문하여 확인한 후 그 노드와 연결된 자식노드 중에서 우선 순위가 가장 빠른 하나를 선택해 방문하며 그후 더 이상 방문할 곳이 없으면 이전 상태로 되돌아가는 탐색 방법이다.이때 탐색 과정이 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(.. 이전 1 다음
