-
[프로그래머스] 타겟 넘버(C++)2024년 01월 19일
- 유니얼
-
작성자
-
2024.01.19.:30
728x90안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "타겟 넘버" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 것이 목표입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.
문제링크 :
https://school.programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 개요
"타겟 넘버" 문제는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 문제입니다. 예를 들어, 숫자들 [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를 증가시킵니다.
결론
이 "타겟 넘버" 문제는 깊이 우선 탐색을 사용하여 효과적으로 해결할 수 있습니다. 이 방법은 모든 가능한 조합을 체계적으로 탐색하면서, 주어진 조건에 부합하는 모든 경우의 수를 찾아냅니다. 이 접근 방식은 다양한 알고리즘 문제에 적용될 수 있으며, 특히 조합적 문제 해결에 유용합니다.
반응형다음글이전글이전 글이 없습니다.댓글