반응형 backtracking1 알고리즘 백트래킹(Backtracking) ●백트래킹 - DFS(깊이우선탐색)방식으로 해를 찾는 방법이다. DFS는 해를 찾기 위해 전진, 후진을 반복한다. 백트래킹 재귀 호출을 해서 구현하면 편리하다. ●깊이우선탐색(DFS, Depth First Search) - 답을 찾을 때 가장 위에서 가장 아래쪽으로 들어 갔다가, 제일 밑에 까지 왔을 때 더 들어갈 곳이 없으면 위로 나왔다가 다시 가장 끝까지 들어가는 동작을 되풀이 한다. 여기서 위로 나오는 동작을 백트래킹이라고 한다 ●스택(stack) - 나중에 입력된 데이터가 먼저 빠져 나오는 구조이다. 후입선출(LIFO) ●사용하는 재귀함수의 수는 수학의 "경우의 수"와 같다. 예를들어 동전,주사위 등의 문제를 코딩할 때 각각의 무제의 경우의 수만큼의 재귀호출을 사용한다. ●백트래킹 알고리즘으로 해.. 2012. 4. 8. 이전 1 다음 반응형