[프로그래머스] 타겟 넘버 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 타겟 넘버 문제입니다.

 

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

 

 

 

해결 과정

 

본 문제는 주어진 배열의 사이즈 만큼 깊이를 탐색해야함으로  DFS 문제로 유추할 수 있습니다.

DFS 구현은 재귀호출를 사용하였습니다. 최종 깊이까지 탐색한 이후 해당 노드의 값이 찾고자 하는 값과

일치한다면 answer의 값을 하나 올려줍니다. 이후 모든 재귀호출이 끝난 이후 answer을 반환합니다.

 

 

 

 

코드 전문

 

#include <vector>

using namespace std;

void DFS(vector<int>& numbers, int& target, int sum, int height, int& answer)
{
    if (height == numbers.size())
    {
        if (sum == target) { answer++; return; }
        else { return; }
    }
    
    DFS(numbers, target, sum + numbers[height], height+1, answer);       
    DFS(numbers, target, sum - numbers[height], height+1, answer);

}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int sum = 0;
    DFS(numbers, target, sum, 0, answer);
    
    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

백트래킹과 DFS의 차이를 아직 잘 모르겠네요!  조금 알아본 결과 백트래킹은 정답을 찾는 중 현재 선택한 루트가 정답과 관련이 없음을 알게되면 해당 루트를 넘기고 이전 단계로 넘어가 다른 루트를 탐색하는 기법이고 DFS는 하나의 가지를 완전히 탐색 한 이후 다음 가지로 넘어가 마져 탐색하는 기법이라고 하네요. 그렇다면 이번 문제는 DFS가 맞습니다! 이후 PS를 열심히 한 이후 저 나름대로의 내공이 쌓인다면 각 기법에 대해 정리하고 싶습니다. 그리고 후배들 한테 알려주고 싶네요! 얏호

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.