Swift Programmer Swift Programmer

백트랙킹(backtracking)순열이나 조합처럼 depth가 유동적인 경우 for로 탐색하기 보다는 재귀를 이용해서 탐색하는게 수월하다. dfs와 차이점은 dfs는 depth 끝까지 탐색하지만 백트랙킹은 해가 아니라고 판단되면 더이상 탐색을 하지않는다.백트랙킹 알고리즘을 이해하기 가장 쉬운 예시가 순열과 조합이다. 순열 - N개중 M개를 순서를 고려하여 뽑는 경우의 수조합 - N개중 M개를 순서를 고려하지 않고 뽑는 경우의 수중복순열 - N개중 M개를 순서를 고려 & 중복 허용중복조합 - N개중 M개를 순서를 고려하지 않음 & 중복 허용순열(Permutation)순열은 순서를 고려하여 경우의수를 나열한다 예를들어 1,2,3 의 수에서 3개의 순열로 경우의수를 나열하면(1,2,3)(1,3,2)(2,1,3..