완전탐색, 모든 경우의 수

완전탐색 같은 경우, 누구나 생각은 할 수 있지만 재귀함수에 약한 글쓴이는 정리를 해보려고 합니다.😅

참고 문제는 프로그래머스 소수찾기입니다.

문제에서는 입력으로 숫자로 된 문자열이 입력됩니다. 예를 들어서 "17", "011"과 같이 입력이 되면 "17"은 "1"과 "7"로 조합할 수 있습니다. 그 수 중에서 소수의 갯수를 답으로 반환하는 문제입니다.

조합을 만드는 소스코드

const makeCombinations = (arr, str) => {
	if (arr.length > 0) {
		for (let i = 0; i < arr.length; ++i) {
			const temp = [...arr];
			temp.splice(i, 1);
			makeCombinations(temp, str + arr[i]);
		}
	}
	if (str.length > 0) {
		if (isPrime(+str) && !primeNumbers.includes(+str)) {
			primeNumbers.push(+str);
		}
	}
};

• arr : 문자들의 배열 ex) [1, 7]
• str : 조합한 문자열

먼저 문자들의 배열, arr을 먼저 검사합니다. arr의 길이가 0보다 큰 경우에는 arr의 첫 번째 원소부터 끝까지 반복문을 진행합니다.
반복문안에서는 temp란 변수 안에 입력받은 arr 원소들을 복사해줍니다. 그리고는 i번째에 해당하는 원소를 지우고 makeCombinations(temp, str + arr[i])를 통해서 temp에서 지운 원소를 str(조합한 문자열)에 더해줍니다.

---

예시) 입력된 문자열 "17"

i = 0일 때, str=""
1. arr[ ... ] ▶︎ temp[ ... ]
2. temp[ ... ] ▶︎ <temp[0]삭제> | temp[1], temp[2], ...
3. str + arr[i] === "" + temp[0] ▶︎ 1

---

재귀함수 호출이 되었으므로 다시 makeCombinations가 작동하게 됩니다. 이를 반복하게 되면 arr에서 slice가 모두 되어 arr.length가 0이 되게 됩니다. 이때 str의 length를 검사하여 0보다 클 때, 소수인지 판별하고 이미 나왔던 수인지 판별한 다음에 없을 경우에만 저장(push)을 해줍니다.😁

함수	arr.length	str.length	primeNumbers
makeCombinations([1,7], "")	2	0	[]
makeCombinations([7], "1")	1	1	[]
makeCombinations([], "17")	0	2	[17]
makeCombinations([1], "7")	1	1	[17]
makeCombinations([], "71")	0	2	[17, 71]
makeCombinations([1], "7")	1	1	[17, 71, 7]

"17"이 입력된 경우에는 배열의 원소 갯수는 총 2개. 발생할 수 있는 조합의 수는 $2^2$, [ 1, 7, 17, 71 ]입니다.

• 처음에 시도한 수는 1, false
• 두번째 시도한 수는 17, true
• 세번째 시도한 수는 71, true
• 네번째 시도한 수는 7, true

한 마디로 조합할 수 있는 부분배열들을 함수의 입력으로 또 사용하니 부분배열안에서의 경우의수가 발생합니다. 트리구조로 그려보면 이해가 쉬울 듯 합니다.