[프로그래머스] 비밀 코드 해독(Lv2) - (C++)백트래킹 문제는 포기 조건 검사가 종료 히트 보다 먼저!

[프로그래머스] LV2 : 2025 프로그래머스 코드챌린지 1차 예선 ::  비밀 코드 해독

 

사내 코딩테스트 합격을 위해. 유연근무제 문제에서 뚜들겨 맞은 기세를 쭉 이어나가봅니다.

↓ Lv1 문제에 개 뚜들겨맞고 정신이 번쩍 든 이야기

2025.07.26 - [개발자 일상/직장인도 코딩 테스트를 준비합니다] - [프로그래머스] 유연근무제(Lv1) - 에헤이.. 3년차가 이런 실수를!

이번 문제풀이에서 배운 것들

새로 배운 것

std::set_intersection

두 개의 정렬된 set나 정렬된 vector에서 교집합을 찾아 정렬된 vector로 반환하는 매서드

• 인자 : 교집합을 찾고 싶은 set나 vecter 각각의 시작/끝 iterater와 교집합을 담을 vector의 iterator(인데 트릭 있음)
• 반환값 : 교집합의 마지막 원소 다음을 가리키는 iterater

🔻Programmers C++ Reference 

https://devdocs.programmers.co.kr/cpp/algorithm/set_intersection

vector<int> A = {1, 2, 3};
vector<int> B = {2, 3, 4};

// 기억하기 쉬운 사용법
vector<int> res(5);

auto r_end = set_intersection(A.begin(), A.end(), B.begin(), B.end(), res.begin());

// 교집합의 원소 개수 확인
cout << r_end - res.begin();

// res vector를 유효 크기로 줄이기
res.resize(res.begin() - r_end);


// "back_inserter" 트릭 사용하기
vector<int> res;

// iterater가 아닌 back_inserter iterator가 제공됨으로서
// iterater가 가리키는 값을 변경하려는 시도가 push_back으로 대치됨
// res는 길이가 0인 빈 vector이지만 자동으로 크기 증가하며 결과를 정상 할당
auto r_end = set_intersection(A.begin(), A.end(), B.begin(), B.end(), back_inserter(res));

// 교집합의 원소 개수 확인
cout << res.size();

 

 

더 주의해야 할 것들

가정을 세우고 싶을 때는 근거를 반드시 찾아두자

잘못 생각한 것 : 입력을 시도한 정수들만 비밀 코드로 쓰일 수 있다고 생각함
추정되는 이유 : 상태 공간의 크기를 줄여야 할 것 같다는 막연한 압박감 때문에 그렇게 믿고 싶었던 것 같음

DFS 기반 백트래킹 함수의 구조는 정형화 하자

삽질의 흐름
1. 단순 탐색 구조로 탈출조건을 제일 위에 잡음
2. 자꾸 후보 배열이 무한증식하는 문제에 걸려서 여기저기 pop_back()으로 때우려고 함
3. 몇대 맞고 이게 아닌가 싶어서 pruning 검사를 먼저 하고 다음 하위상태를 요청하도록 그제서야 바꿈

 

단순 탐색

void dfs(...)
{
    if(EndConditionReached()) return;   // 탈출 조건 먼저
    ActionForThisCombination();         // 방문 기록 등
    for (SubCombination() : ...)
    {
        dfs(...);
    }
}

• 경계 조건 검사
• 요청된 조합에 대해 검사
• 하위 조건 검사 요청

pruning이 필요한 경우(Backtracking)

void backtracking(...)
{
    if(ConditionAlreadyFailed()) return;
    if(EndConditionReached()) return;
    ActionForThisCombination();
    for(SubCombination() : )
    {
    	backtracking(...);
    }
}

• 요청된 조합에 대해 검사
• 경계 조건 검사
• 하위 조건 검사 요청

백트래킹을 위한 "하위 상태 탐색 중단 조건" 명확하게 생각하고 설정하기

삽질의 흐름
1. 1개 골라놓고 교집합의 개수가 ans[i]와 다르다고 검색 포기하게 만듬
2. 앞으로 최선을 골라도 안 되는 경우만 반영
3. 이미 교집합의 개수가 초과되는 경우를 그제서야 조건에 반영

자세한 풀이 흐름 기록

문제 분석

상태 공간의 크기

사실 저도 처음 문제를 보고 'n이 30이나 될 수 있으면 가지치기가 필요하겠다' 라고 생각했습니다.

약간은 과한 걱정인게, 이건 순열이 아니라 조합이라서 그렇게 상태공간이 크지 않다는 것이죠

 

순서에 관계없이 30개 숫자 중에 5개의 숫자를 고르는 경우의 수

30C5 = 142506

 

그래서 "브루트포스형 완전탐색" 으로도 시간초과가 나지 않습니다.

 

🧠 가지치기가 필요한 이유는 "시간"이 아니라 "논리"

그럼에도 불구하고 가지치기를 하는 이유는

논리적으로 이미 실패한 하위 상태들을 굳이 코드 짜는 데 고려할 이유는 없기 때문입니다.

네, 쉽게 말하자면 "내 머리가 편한것"이 중요한거죠.

가지치기를 하면 탐색공간도 코드도 불필요한 탐색을 고려하지 않아도 되게 됩니다.

 

📌 프로그래머스 Tip

실제로 가지치기가 잘 되어 있으면 프로그래머스 기준 탐색 문제에서 cout을 활용한 디버깅에도 유리합니다.

전체 탐색 공간의 크기가 줄어 "출력이 너무 깁니다" 오류를 만날 가능성이 줄어들기 때문이에요.

문제 접근

문제는 아래의 두 과정을 통해 아주 정직하게 풀 수 있습니다.

• 후보 비밀 코드 선택
• 해당 비밀코드가 문제의 입력으로 주어진 q[i]와 비교했을 때 ans[i]와 같은 개수의 숫자가 겹치는 지 확인

가지치기 조건 설정

가지치기의 조건은 추상적으로 봤을 때 크게 두 가지 범주로 나눌 수 있습니다.

• 이번생은 망했어 케이스 : 이미 실패해버린 경우
• 닥터 스트레인지 케이스 : 미래에서 모든걸 최선으로 고르더라도 실패하는 경우

이 문제에서 구체적으로 어떻게 적용되는지 각각 하나씩 예시를 들어서 살펴보겠습니다.

 

🍃 가지치기 예시 1 — 이미 실패한 상태(이번생은 망했어 케이스)

비밀 코드 후보를 만들면서 숫자 1, 2, 3, 4를 고른 상태라고 생각해봅시다.

그리고, 해독 시도 2, 3, 4, 5, 6에 대해서 비밀 코드에 해당하는 숫자의 개수가 2개라고 알려져있다면

{1, 2, 3, 4}와 {2, 3, 4, 5, 6}의 교집합은 {2, 3, 4}로 이미 비밀 코드에 해당하는 숫자의 개수가 3개가 됩니다.

 

이러면 하위 상태인 {1, 2, 3, 4, 5}, {1, 2, 3, 4, 6}, ... 에 대해서는

겹치는 숫자의 개수가 더 늘어나면 늘어나지 줄어들지는 않을거라서 하위 상태들은 굳이 살펴 볼 필요가 없게 됩니다.

 

🔮 가지치기 예시 2 — 미래에서도 실패 확정(닥터 스트레인지 케이스)

동일하게 비밀 코드 후보를 만들면서 숫자 1, 2, 3, 4를 고른 상태라고 생각해봅시다.

이번에는, 해독 시도 2, 3, 4, 5, 6에 대해서 비밀 코드에 해당하는 숫자의 개수가 5개라고 알려져있다면

동일하게, {1, 2, 3, 4}와 {2, 3, 4, 5, 6}의 교집합은 {2, 3, 4}로 비밀 코드에 해당하는 숫자의 개수는 3개가 됩니다.

 

이 경우에는 하위 상태인 {1, 2, 3, 4, 5}, {1, 2, 3, 4, 6}, ... 무엇을 고르더라도

{2, 3, 4, 5, 6}과의 교집합의 크기는 5가 되지 못한다는 것이죠.

최대로 겹치게 할 수 있는 숫자의 개수는 1개이기 때문에 이미 3개를 확정지은 상태이서 3+1인지 3+0인지 살펴볼 필요가 없게 됩니다.

따라서 위에서와 동일하게 하위 상태인 {1, 2, 3, 4, 5}, {1, 2, 3, 4, 6}, ... 에 대해서는 굳이 살펴 볼 필요가 없게 됩니다.

 

그러면 바로 코드로 적어보겠습니다.

모든 TC 통과한 코드

백트래킹이 적용된 버전

위에서 설계한 내용이 모두 담긴 코드입니다.

구현량은 정말 적은 것이 프로그래머스식 문제의 특징이죠.

 

시험장에서  set_intersection() 매서드가 떠오르지 않는다면

특정 컨테이너나 특정 매서드를 쓰지 않았다고 떨어지는 문제를 내지는 않으니

투 포인터든, unordered_map이든 사용해서 풀면 됩니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int answer = 0;
vector<int> selected;

void backtracking(int depth, int lastIdx, const vector<vector<int>> &q,
	const vector<int> &ans, int n)
{    
    // 이번 조합에 대해서 검사 수행
    for(int i=0; i<q.size(); i++)
    {
    	// i번째 "암호 분석 시도" q[i]에 대해서
        vector<int> res;
        // q[i]와 후보 암호 selected를 비교했을 때
        set_intersection(q[i].begin(), q[i].end(), selected.begin(),
        	selected.end(), back_inserter(res));
		
        // FAIL 1 : 매칭되어야 하는 숫자의 수 > 이미 맞춘 숫자의 수 + 앞으로 최대로 더 맞출 수 있는 숫자의 수
        // FAIL 2 : 매칭되어야 하는 숫자의 수 < 이미 맞춘 숫자의 수
        if(ans[i] >= res.size() + (5 - depth + 1) || ans[i] < res.size())
        {
            return;
        }
    }
    
    // 검사를 통과했고, 5개의 원소를 선택했다면
    // -> 비밀 코드 후보에 해당
    if(depth == 5)
    {
        answer++;
        return;
    }
    
    // 검사를 통과했고, 아직 5개가 안된다면
    // -> 아직 고르지 않은 숫자를 하나 골라 다시 검사 요청
    for(int i=lastIdx + 1; i<=n; i++)
    {
        selected.push_back(i);
        backtracking(depth+1, i, q, ans, n);
        selected.pop_back();
    }
    
    return;
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    
    backtracking(0, 0, q, ans, n);
    
    return answer;
}

백트래킹이 적용되지 않은 버전

백트래킹을 적용하지 않으면 코드가 더 심플해집니다.

 

미래를 예측하지 않고 현재 조건만 정직하게 검사하면 되기 때문에

검사 실패 조건이 대소비교에서, 같은지 아닌지 비교하는걸로 훨씬 간단해지게 됩니다.

#include <string>
#include <vector>

using namespace std;
int answer = 0;
vector<int> selected;

void backtracking(int depth, int lastIdx, const vector<vector<int>> &q,
	const vector<int> &ans, int n)
{    
    // 5개의 원소를 선택했다면 -> 비밀 코드 후보 검증
    if(depth == 5)
    {
        for(int i=0; i<q.size(); i++)
        {
        	// i번째 "암호 분석 시도" q[i]에 대해서
            vector<int> res;
            // q[i]와 후보 암호 selected를 비교했을 때
            set_intersection(q[i].begin(), q[i].end(), selected.begin(),
            	selected.end(), back_inserter(res));
			
            // FAIL : 매칭 갯수가 입력과 다른 경우
            if(ans[i] != res.size()) return;
        }
        answer++;
        return;
    }
    
    // 검사를 통과했고, 아직 5개가 안된다면 -> 아직 고르지 않은 숫자를 하나 골라 다시 검사 요청
    for(int i=lastIdx + 1; i<=n; i++)
    {
        selected.push_back(i);
        backtracking(depth+1, i, q, ans, n);
        selected.pop_back();
    }
    
    return;
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    
    backtracking(0, 0, q, ans, n);
    
    return answer;
}

시간 차이는?

가지치기 미적용(왼쪽)과 적용(오른쪽)의 시간차이

🚨 교훈

• 가지치기 조건은 명확하게, 또 명확하게
• 재귀 기반 백트래킹은 백트래킹 조건 검사 먼저하고 그 다음에 종료 조건 hit 확인
• 섣불리 가정 세우지 말자

💭 후기

문제보다 제 자신이 더 문제였네요.
가지치기 조건 하나 제대로 못 잡고 set_intersection만 바라보다가  
닥터 스트레인지한테 고개 숙인 한 시간이었습니다.

이번생은 망했어...  
같은 줄 알았는데, 다행히 return 전에 정신을 차리고 모든 TC "ALL PASS" 했습니다.

Adiue!