프로그래머스 코딩 연습 level 2-타켓 넘버

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

정답:

#include <string>
#include <vector>

using namespace std;
int answer=0;
void dfs(vector<int> numbers, int target,int num,int sum,int count){
    
    if(numbers.size()==count){
        if(target==sum){
            answer++;
    }
        return;
    }
    
   
    dfs( numbers,  target, num,sum+numbers[count],count+1);
    
  
   
    dfs( numbers,  target, num,sum-numbers[count],count+1);
    
    }

int solution(vector<int> numbers, int target) {
    
    int count=0;
    int sum=0;
    int num=numbers.size();
     dfs( numbers,  target, num,sum,count);
    return answer;
}

200813

다시 푸는데 기억 안나서 결국 내가 풀엇던걸 다시 봣는데 어떻게 이렇게 생각햇지 하면서 

풀고잇다 비슷하겐 만들었는데 생각을 잘못한것같다.

 

현재 풀고 잇으나 어떻게 접근해야하는지 감이 안옴

#include <string>
#include <vector>
#include<iostream>
using namespace std;

struct Save{
    int num;
    bool bCheck;
};
vector<Save> save;
int count=0;
int Bfs(int index,int dataNum,int sum,int target){
    
    
    if(index>=dataNum){
        cout<<endl;
        if(sum==target){
            return 1;
        }else {
            return 0;
        }
        
        
    }
    
    index=index+1;
    
    if(save[index].bCheck==false){
        save[index].bCheck=true;
        sum+=save[index].num;
        
        cout<<"+"<<save[index].num;
        
        
      count  =count+Bfs(index,dataNum,sum,target);
    }
    
    if(save[index].bCheck==true){
        save[index].bCheck=false;
        sum-=save[index].num;
         
           cout<<"-"<<save[index].num;
         count= count+Bfs(index,dataNum,sum,target);
    }
    
    return count;
    
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    int sum=0;
    
    for(int i=0;i<numbers.size();i++){
        Save tmpSave;
        tmpSave.num=numbers[i];
        tmpSave.bCheck=false;
        save.push_back(tmpSave);
      
    }
    answer=Bfs(-1,numbers.size(),sum,target);
    
  
    
    return answer;
}

지난번이 훨씬 간단하게 푼것같다 이번껀 잘 못푼데다가 접근도 좀 잘못된것같다.

재귀함수랑 dfs를 사용해야한는데 

파라미터 넘기는 방법에 대한 아이디어가 부족한듯 싶다.

200814

#include <string>
#include <vector>
#include<iostream>
using namespace std;
 int answer = 0;
 
void Dfs(vector<int> numbers, int target,int size,int data,int count){
    
    if(numbers.size()==count){
        if(target==data){
            answer++;
        }
        
        return ;
    }
  
    
  Dfs(numbers, target,size,data+numbers[count],count+1);
      
  Dfs(numbers, target,size,data-numbers[count],count+1);
    
    
    return ;
    
}
int solution(vector<int> numbers, int target) {
   
int count=0;    
 int data=0;  
int size=numbers.size();
 Dfs(numbers, target,size,data, count);
    

    
 return answer;
    
}

 

주의점  함수 파라미터를(맴버 변수)를 넘길때 계산을 함수 파라미터에서 계산해주면 현재 함수에 영향이 가지 않는다

즉 다음 파라미터에 영향이 간다 . 재귀함수 특징중 하나라 볼수 잇는데 이게 생각보다 좀 이해가 어렵다

  Dfs(numbers, target,size,data+numbers[count],count+1);

쉽게 설명하자면 예를 들어 count의 경우에 0이라고 할때 

첫번째 함수내에선 0으로 계산이된다 즉 count+1 을 하게 되면 다음 함수에서 더해진값으로 진행된다.

그렇다면 count++ , ++count 은 왜 안되는가이다. count++이랑 ++count 차이는 당연히 알거라 생각하지만

다시한번 설명드리자면 ++count는 그 라인에서 계산된 상태이고 , count++는 다음 줄에서 계산 된 상태가 된다

그렇다면 필자도 실수했던게  ++count하면되겟지 하고 생각햇다 문제는 내 커다란 착각이엇다

그렇게 되면 일단 이함수내의 count는 +1이 되어버린다.  그렇기 때문에 올바른 형태로 계산되지 않는다.

그러므로 count+1을 해서 현재 함수에는 0으로 count를 유지하고 다음 재귀를 탄 파라미터 count가 1이 되어서 계산되야한다 

기초중에 기초이며 정말 중요한 내용이다.

 

201006 

 

가장 깊이 우선탐색의 기본적인 문제 인것같다.

재귀함수의 이해와 어떻게 동작되는지 이해다.  

#include <string>
#include <vector>
#include<iostream>
using namespace std;
int showCount;
void Dfs(vector<int> numbers, int target,int data,int size,int count){
    if(count>=size){
        if(data==target){
            showCount++;  
        }
        return ;
    }
    
  Dfs(numbers,target,data+numbers[count],size,count+1);
    
     
    
   Dfs(numbers,target,data-numbers[count],size,count+1);

   
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    showCount=0;
    
   Dfs( numbers, target,0,numbers.size(),0);
    //cout<<endl;
   // cout<<showCount;
    return showCount;
}

이런 식으로 가지 치듯 함수가 움직인다. 

정말 몇번을 공부해도 바로바로 적응하는데 시간이 걸리는듯하다