나는 재귀에 약하다..
그래서 백트래킹이 어렵다
이 문제는 완전탐색으로 풀었었는데 지피티를 통해서 백트래킹으로 푸는 로직을 알게되었다. 백트래킹이 완전탐색보다 효율성도 좋고 빠르니 익숙해지면 코드를 쓸 때 도움이 많이 된다.
그래서 백트래킹 코드를 뜯어보며 재귀 감각을 익히고자 한다!
< 🔑 백트래킹에서 중요한 포인트 >
-
재귀적으로 결정
→ 문제를 한 단계씩 분해하면서 선택지를 좁혀감. -
조건을 만족하지 않으면 더 이상 탐색하지 않음
→ 가지치기 (pruning) -
상태 복구 (undo)
→ 선택했던 것을 pop하거나 사용 여부를 false로 되돌림
이 문제도 백트래킹으로 풀기 위해 구조화한다.
재귀 함수 인자:
-
start: 탐색을 시작할 인덱스
-
count: 지금까지 고른 숫자의 개수
-
sum: 지금까지 고른 숫자의 합
종료 조건:
- count == 3이면 sum이 소수인지 확인
반복 / 가지치기:
-
i를 start부터 순회
-
중복을 피하기 위해 그 다음 인덱스부터 재귀 호출
[지피티 코드 (백트래킹)]
#include <vector>
#include <iostream>
using namespace std;
int answer = 0;
bool isPrime(int num) {
if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
void backtrack(vector<int>& nums, int start, int count, int sum) {
if (count == 3) {
if (isPrime(sum)) answer++;
return;
}
for (int i = start; i < nums.size(); i++) {
backtrack(nums, i + 1, count + 1, sum + nums[i]);
}
}
int solution(vector<int> nums) {
answer = 0;
backtrack(nums, 0, 0, 0);
return answer;
}
[내가 쓴 코드 (완전탐색)]
#include <vector>
#include <iostream>
using namespace std;
bool sosu(int a, int b, int c) {
int tmp = a+b+c;
for(int i=2; i*i<=tmp; i++) {
if (tmp%i==0) return false;
}
return true;
}
int solution(vector<int> nums) {
int answer = 0;
for(int i=0; i<nums.size(); i++) {
for(int j=i+1; j<nums.size(); j++) {
for(int k=j+1; k<nums.size(); k++) {
bool isSosu = sosu(nums[i], nums[j], nums[k]);
if (isSosu)
answer++;
}
}
}
return answer;
}