모든 경우의 수를 시도하여 정답을 찾는 방법이다. 무식하게 푼다는 의미로 Brute Force라고도 한다. 상대적으로 간단한 방법이지만 경우의 수가 많아지면 시간이 오래걸린다는 단점이 있다.
재귀(Recursion)은 자기 자신을 호출한다는 뜻이다. 뜻에서 알 수 있듯이 재귀함수는 자기 자신 함수를 호출하여 작업을 수행한다.
사이클
발생하지 않아야 함무한 루프
에 갇히고 스택 오버플로우가 일어난다. n!
n!/(r-1)!
= nPrjava로 구현한 순열 - 재귀함수 사용
public class PermutationMain {
//순열 구하기
public static void Permutation(String[] arr, int start, int end) {
if(start == end) {
for(String i : arr) {
System.out.print(i+" ");
}
System.out.println("");
}
else {
for(int i = start; i <= end; ++i) {
swap(arr, start, i);
Permutation(arr, start+1,end);
swap(arr, start, i);
}
}
}
//인덱스 원소 바꾸기
public static void swap(String[] arr, int a, int b) {
String temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
//예시) arr = ["A", "B", "C"] 순열 출력
public static void main(String[] args) {
String[] arr = new String[] {
"A", "B", "C"
};
Permutation(arr, 0, arr.length-1);
}
}
출력
A B C
A C B
B A C
B C A
C B A
C A B
}
작동원리 그림
참고사이트