프로그래머스 깊이/너비 우선 탐색 타켓 넘버 c++ 풀이

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]

3

5

입출력 예 설명

문제에 나온 예와 같습니다.

 

문제 예시 보고 재귀함수로 풀어야지 하고 풀었다

vector<int> NUMBERS;
int TARGET;
int ANSWER = 0;

void recursive(int index, int total)
{
    if (index == NUMBERS.size())
    {
        if (total == TARGET)
            ++ANSWER;
        return;
    }
    recursive(index + 1, total + NUMBERS[index]);
    recursive(index + 1, total - NUMBERS[index]);
}

int solution(vector<int> numbers, int target)
{
    NUMBERS = numbers;
    TARGET = target;

    recursive(0, 0);

    return ANSWER;
}

한 번에 통과했다.

 

 

이제 껏 푼 문제들 중 제일 빨리 푼 것 같다. 시행착오가 없어서 인 듯...

이제 c++에 쫌 익숙해진걸까ㅎㅎ

그런데 아직 stl 라이브러리가 익숙하지 않아서 한 번 쭉 보고 싶은데 책을 한 번 사볼까 싶다 🤔

카테고리가 깊이/너비 우선 탐색인데 그게 뭔지 가물가물해서 찾아보기로 했다.

그래프를 탐색하는 방법 어쩌고 하는데 둘 다 전탐색의 일종인 듯 하다.

깊이 우선탐색은 시간이 오래걸리는 대신 메모리 사용이 적고,

너비 우선탐색은 시간이 짧게 걸리는 대신 메모리 사용이 많다.

너비 우선탐색을 사용하는건 주로 최단거리 찾을 때이다.

찾고보니 내가 쓴 방법은 깊이 우선탐색인듯.. 재귀함수가 전형적인 깊이 우선 탐색 방법이라고 한다. 분명 배웠을텐데...

일단 이정도만 알아보고 다른 사람 코드를 봤다.

 

다른 사람 코드 분석

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = 1 << numbers.size();

    for(int i = 1 ; i < size ; i++){
        int temp = 0;
        for(int j = 0 ; j < numbers.size() ; j++)
        {  
            if(i &(1 << j)){
                temp -= numbers[j];
            }
            else temp += numbers[j];
        }
        if(temp == target) answer++;
    }
    return answer;
}

2^size 만큼 돌면서 더하고 빼고 하는 거다. 같은 전탐색이라 시간 효율성은 같을 것이다.

비트연산자를 써서 되게 있어보인다.

int total;

void DFS(vector<int> &numbers, int &target,int sum,int n) {
    if(n >= numbers.size()){
        if(sum == target) total++;
        return;
    }

    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}

이건 나랑 똑같은 로직이다. 다만 이 분은 벡터를 전역으로 안빼고 참조를 넘겨줬다.

ㅇㄴ 씨플플 수업 들은거 다 까먹었냐고... 나도 이렇게 할걸

 

ㅇㄴ 씨플플 수업 들은거 다 까먹었냐고... 나도 이렇게 할걸

 

bool promising(int depth, const vector<int> &numbers, int search, int target) {
    int lastSum = 0;
    for (int i = depth; i < numbers.size(); i++) {
        lastSum += numbers[i];
    }

    if (search + lastSum < target || search - lastSum > target) {
        return false;
    }
    else return true;
}

void searchNum(int &answer, int depth, const vector<int> &numbers, int search, int target) {
    if (promising(depth, numbers, search, target)) {
        if (depth == numbers.size()) {
            answer++;
            return;
        }

        search += numbers[depth];
        searchNum(answer, depth + 1, numbers, search, target);

        search -= (2 * numbers[depth]);
        searchNum(answer, depth + 1, numbers, search, target);
    }
}

int solution(vector<int> numbers, int target) {

    int answer = 0;

    searchNum(answer, 0, numbers, 0, target);

    return answer;
}

 

이번에 시간이 남아서 더 보다가 promising이 뭐지? 싶어서 가져왔다.

프로미싱이란 깊이 우선탐색의 백트래킹 세부 절차로 '유망성 검사' 라고 한다.

시간 단축을 위해 해가 나올 가능성이 없으면 백트래킹하여 조사하지 않는 것인데, 이 문제의 경우엔 해당 인덱스까지 계산한 값과 그 인덱스 이후 숫자들을 다 더하거나/다 뺐을 때 타겟 넘버보다 작거나/크면 해가 될 가능성이 없으므로 조사를 중단하는 것이다.

 

코드 가져온 순서가 좋아요 순서대로인데, 마지막의 경우엔 내가 누른 좋아요까지 총 네개밖에 안된다.

겉멋만 잔뜩 들어서 비트연산자 쓴 코드보다 마지막이 훨씬 도움되는데... 코드 노출 알고리즘을 좀 바까주세요~~