📖 TIL - 재귀와 백트래킹으로 풀어보는 소수 찾기 🧩

📌 문제 설명

주어진 숫자 배열에서 3개의 수를 선택하여 더했을 때 소수가 되는 경우의 수를 구하는 문제

입력

• 숫자 배열 nums

출력

• 3개의 수를 더해서 소수가 되는 경우의 수를 반환

예시

nums = [1,2,3,4]
// 가능한 조합: [1,2,4], [1,3,4]
// 출력: 2

🤔 문제 접근

1. 3중 for문 접근

   function solution(nums) {
     let answer = 0;
     let size = nums.length;
     
     for(let i = 0; i < size; i++) {
       for(let j = i+1; j < size; j++) {
         for(let k = j+1; k < size; k++) {
           const sum = nums[i] + nums[j] + nums[k];
           if(isPrime(sum)) answer++;
         }
       }
     }
     return answer;
   }

2. 백트래킹 접근

   function solution(nums) {
     let answer = 0;
     
     function findCombinations(selected, startIdx) {
       if(selected.length === 3) {
         const sum = selected.reduce((a,b) => a+b, 0);
         if(isPrime(sum)) answer++;
         return;
       }
       
       for(let i = startIdx; i < nums.length; i++) {
         selected.push(nums[i]);
         findCombinations(selected, i+1);
         selected.pop();
       }
     }
     
     findCombinations([], 0);
     return answer;
   }

💡 해결 방법

1. 소수 판별 함수 최적화

   function isPrime(num) {
     // i*i <= num으로 최적화
     for(let i = 2; i*i <= num; i++) {
       if(num % i === 0) return false;
     }
     return true;
   }

2. 백트래킹을 통한 조합 생성

   • 선택된 숫자를 배열에 추가
   • 재귀 호출로 다음 숫자 선택
   • 백트래킹으로 이전 상태로 복귀

🔍 코드 설명

백트래킹 동작 과정

1. 빈 배열 []로 시작
2. 첫 번째 숫자 선택 후 배열에 추가
3. 재귀적으로 다음 숫자 선택
4. 3개가 선택되면 합을 계산하고 소수 판별
5. 이전 상태로 돌아가서 다른 조합 시도

소수 판별 최적화

• 제곱근까지만 확인하여 효율성 향상
• 예: 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36
• √36 = 6을 기준으로 대칭이므로 6까지만 확인

✨ 새롭게 배운 점

1. 백트래킹의 개념과 활용

   • 가능한 모든 경우를 체계적으로 탐색
   • 불필요한 탐색을 제거하여 효율성 향상
   • 결정 트리를 통한 문제 해결

2. 재귀 함수의 장점

   • 복잡한 반복문을 간단하게 구현
   • 코드의 가독성 향상
   • 상태 관리가 용이

3. 소수 판별 최적화

   • 제곱근 활용으로 연산 횟수 감소
   • 수학적 개념을 코드에 적용

🚀 이런 점이 효율적이에요

• 재귀를 통한 깔끔한 코드 구현
• 백트래킹으로 불필요한 연산 제거
• 소수 판별 최적화로 성능 향상
• 확장성 있는 코드 구조 (n개 선택으로 쉽게 확장 가능)

⭐️ 참고 자료

• 백트래킹 알고리즘의 이해
• 소수 판별 알고리즘 최적화 방법
• JavaScript 재귀 함수 활용법