1. 개요 [그림 1] 백 트래킹(Backtracking) 과정 백트래킹의 주요 개념은 해를 얻을 때까지 모든 가능성을 시도하는 기법이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에서 해결책을 찾는다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아가고 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 여러 시도중 해결 방법이 더이상 없으면 더 이전의 분기점으로 돌아가고 모든 트리의 노드를 검사해도 답을 찾지 못할 경우, 이 문제의 해결책은 없는 것으로 간주한다. 1. 어떤 노드의 유망성을 점검한 후에 유망(Promising)하지 않다고 결정되면 그 노드의 부모로 돌아가 (backtracking) 다음 자식 노드로 감 2. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 ..
1. 개요 [그림 1] 분할 정복법 ( Divide and conquer ) 알고리즘 방법론중 하나인 분할정복 ( Divide and conqeur ) 알고리즘은 하나의 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 보통 재귀함수 ( Recursive function )을 이용해서 구현하는 것이 일반적이나 빠른 실행이나 부문제 해결 순서 선택을 위해 재귀호출을 사용하지 않고 스택(Stack), 큐(Queue) 등의 자료구조를 이용하여 분발 정복법을 구현하는 것도 가능하다. 분할 정복의 설계전략으로는1. 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.2. 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.3. 통합 (Combine) : 해결된..
1. 개요 [그림 1] 재귀호출의 과정 재귀적 호출 함수 ( Recursive call ) 란 작업을 작은 단위로 쪼개서 재귀 호출된 함수 내에서 이 조각중에 하나를 해결하고, 나머지 조각들은 자기 자신을 또 호출해서 해결하는 방식으로 처리되는 함수로 간단히 말해서 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수이다.재귀호출함수를 구현하려면 2가지 부분이 필요하다. 하나는 기본 부분 (Base part)와 유도 부분 (Inductive part)이다. 기본 부분은 재귀호출이 나중엔 결국 끝이 나야하므로 종결조건을 위한 부분이고 유도 부분은 새로운 집합의 원소를 생성하기 위해 재귀하는 부분이다. 재귀적 프로그래밍은 일반 반복 ( for,,while...등 ) 프로그래밍에 비해 간결하다는 점이..