코테 / 프로그래머스 타겟 넘버(재귀함수 이해하기)

출처 : https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84C-BFSDFS

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

 

문제 설명이랑 더 자세한 설명은 위에 있다.

 

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

// 전역변수 answer
int answer = 0;
int idx = 0;
void get_target_number(vector<int> numbers, int target, int sum, int index){
    //종료 조건
    if (index == numbers.size()){
        if (sum == target) {
            cout << "in" << "\n";
            cout << "index : " << index << '\n';
            answer++;
        }
        // 같지 않을때도 return
        cout << "index : " << index << '\n';
        cout << "not in" << "\n";
        return;
    }
    cout << "idx : " << index <<'\n';
    idx += 1;
    //종료 조건이 만족되지않으면 계속 탐색
    get_target_number(numbers, target, sum + numbers[index], index + 1);
    get_target_number(numbers, target, sum - numbers[index], index + 1);
}

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

    return answer;
}

1. main 함수에서 get_target_number 호출

처음으로 호출하면 sum, index 모두 0

index가 사이즈랑 다르니까 idx : 0 출력하고 idx = 1되고, 다시 get_target_number(~~, sum + ~~~) 호출

 

2. 재귀함수 진입

main에서 처음 부른 함수 내에서 다시 get_target_number를 부른 모양이다. 그래서 아직 main에서 호출한 get_~함수를 빠져나가지 못했다. main에서 부른 함수는 이 코드의 가장 마지막에 return된다.

 

3. idx 1인 상황

main 함수에서 부른 get_target으로 idx가 1로 증가했고, 다시 진입했을 때에도 마찬가지로 if문을 만족하지 못하니 idx는 1증가한 2가 된다. 그리고 다시 get_target_number로 진입한다.

그럼 main(get_(get_())) 모양이다. 이걸 풀기 위해서는 무조건 index(idx랑 다름)가 size()와 같아져서 return을 만나 첫번째 get_()에 돌아가야 한다. 첫번째 get_()도 return을 만나야 빠져나갈 수 있다.

 

4. idx 2인 상황

3과 마찬가지로 return을 만나지 못하고 idx만 증가한다.물론 index도 증가한다.

 

5.쭉 증가해 index가 size()와 같아진 상황

여기서 index 값은 5가 들어온다. 당연히 인자로 1 더해서 줬으니까 5다.

근데 그 전 함수에서는 index가 4다. 전 함수의 전 함수가 3에 1을 더해서 줬으니까.

 

[1,1,1,1,1], target = 3인 상황에서, 여기까지 오면 sum은 5가 된다.

그리고 if문을 만족해 sum이 target이랑 같은지를 비교한다.

다르니까 index와 not in을 출력하고 return한다. 그러면 main(get_(get_(...get_())))에서 제일 안쪽 get_()함수에서 그 전 함수로 return하게 된다. 이 때 index는 4가된다. 왜냐면 인자로 index에 1을 더해서 주기 전 상황으로 돌아간거다. 여기서 sum도 마찬가지로 4이다. sum이 index와 마찬가지로 변수로 선언된게 아니기 때문에 값이 이전으로 돌아갈 수 있다.

 

6. get_~~(~~,sum - ~~, index+1); 만나기

5번에서 return을 만나 index가 4인 세계로 돌아왔다. 지금 위치가

get_target_number(numbers, target, sum + numbers[index], index + 1); 여기를 끝내고
get_target_number(numbers, target, sum - numbers[index], index + 1); 여기를 index = 4가 들어간다. 

5에서와 마찬가지로 sum은 4인 상황이다.

 

7. sum 값은 빼고, index는 다시 5

6번에서 다시 재귀 함수를 들어가 index가 5라서 if문을 만족하고 sum은 4에서 1이 빠져 3이 된다. 

그럼 answer가 올라가고, not in을 의미없이 출력하고 return한다. return하면 다시 index가 4인 세계로 돌아간다. 

 

8. 7번의 결과로 하나를 return해 index가 4이고 sum은 3이다. 7번까지는 머리로 계산이 되는데 여기선 헷갈리니까 트리를 그려보자.

 

이 그림에서 index는 깊이를 의미한다. 1,2,3, 4, 5

다시 7번의 끝 상황을 생각해보자. 위 그림으로 이해하면 5 index에서 sum 3을 만나서 answer를 더하고 4로 리턴한다(7번의 리턴). 리턴의 결과는 index 4, sum 4이다. 

이 상황에서 

get_target_number(numbers, target, sum - numbers[index], index + 1); 여기를 들어간다.

따라서 index는 5이고 sum은 3이된다.

 

9. 다시 return 

8번 상황에서 answer를 하나 더하고 다시 return해 index는 4, sum은 2가 된다. 

이 상황에서

get_target_number(numbers, target, sum - numbers[index], index + 1); 여기를 들어간다.