[프로그래머스] 타겟 넘버(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "타겟 넘버" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 것이 목표입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

문제 개요

"타겟 넘버" 문제는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 문제입니다. 예를 들어, 숫자들 [1, 1, 1, 1, 1]과 타겟 넘버 3을 사용할 때, 가능한 조합은 5가지입니다.

문제 해결 전략

이 문제의 핵심은 모든 가능한 덧셈과 뺄셈의 조합을 탐색하는 것입니다. 이를 위해 깊이 우선 탐색(DFS) 알고리즘을 사용합니다. DFS는 각 숫자에 대해 더하거나 빼는 모든 경우를 탐색하며, 타겟 넘버에 도달할 때마다 카운터를 증가시킵니다.

코드 구현

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// DFS 함수는 깊이 우선 탐색을 이용하여 문제를 해결합니다.
// numbers: 사용할 숫자들이 담긴 배열
// curIndex: 현재 처리 중인 numbers 배열의 인덱스
// target: 만들고자 하는 타겟 넘버
// sum: 현재까지의 누적 합계
// count: 타겟 넘버를 만드는 방법의 수를 카운트하는 변수
void DFS(vector<int> &numbers, int curIndex, int target, int sum, int &count) {
    // 모든 숫자를 고려했을 때,
    if (curIndex >= numbers.size()) {
        // 현재까지의 합계가 타겟 넘버와 동일한 경우, 카운트 증가
        if (sum == target) {
            count++;
            return;
        }
        return;
    }
    // 현재 숫자를 더하는 경우의 재귀 호출
    DFS(numbers, curIndex + 1, target, sum + numbers[curIndex], count);
    // 현재 숫자를 빼는 경우의 재귀 호출
    DFS(numbers, curIndex + 1, target, sum - numbers[curIndex], count);
}

// solution 함수는 주어진 문제를 해결하는 메인 함수입니다.
// numbers: 사용할 숫자들이 담긴 배열
// target: 만들고자 하는 타겟 넘버
int solution(vector<int> numbers, int target) {
    int answer = 0; // 타겟 넘버를 만드는 방법의 수를 저장할 변수
    // DFS 함수를 호출하여 타겟 넘버를 만드는 모든 방법 탐색
    DFS(numbers, 0, target, 0, answer);
    return answer; // 결과 반환
}

코드 설명

위 C++ 코드는 DFS를 사용하여 문제를 해결합니다. DFS 함수는 현재 인덱스(curIndex), 현재까지의 합(sum), 타겟 넘버(target), 그리고 가능한 조합의 수를 저장하는 count를 매개변수로 받습니다. 배열의 모든 요소를 고려할 때까지 재귀적으로 함수를 호출하며, 각 단계에서 현재 숫자를 더하거나 뺍니다. 만약 모든 숫자를 사용한 후 총합이 타겟 넘버와 일치하면 count를 증가시킵니다.

결론

이 "타겟 넘버" 문제는 깊이 우선 탐색을 사용하여 효과적으로 해결할 수 있습니다. 이 방법은 모든 가능한 조합을 체계적으로 탐색하면서, 주어진 조건에 부합하는 모든 경우의 수를 찾아냅니다. 이 접근 방식은 다양한 알고리즘 문제에 적용될 수 있으며, 특히 조합적 문제 해결에 유용합니다.