99클럽 코테 스터디 11일자 TIL + 타겟 넘버

문제 출처

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

학습 키워드

DFS/BFS

시도 방법

(1) 재귀로 풀었는데 이게 DFS 였어.

내가 작성한 코드

재귀를 이용한 풀이

이번 문제의 주제는 DFS/BFS 이다.
일단 DFS/BFS 방법을 모른다는 가정하에 재귀를 이용해 문제를 풀 수 있었다.
어 근데.. DFS 포맷이 내가 재귀로 푼 방식이랑 똑같은데?

class Solution {
    int count = 0 ; 
    public int solution(int[] numbers, int target) {
        recursive(numbers , target , 0 , 0);        
        return count; 
    } 
    
    public void recursive(int[] numbers , int target , int index , int now) {
        
        if(index == numbers.length) {
            if(now == target) count++ ;             
            return; 
        } 
        
        recursive(numbers, target , index+1 , now + numbers[index]);
        recursive(numbers, target , index+1 , now - numbers[index]);        
    }
}

코드설명

numbers 에 [4,1,2,1] 이 있고 타겟이 4라고 가정해보자.
처음 recursive를 호출할때 각각 numbers 배열 , 타겟 , 인덱스 , 최근연산값을 매개변수로 준다.

recursive-0 일 때 아래와 같이 두번의 재귀 호출 발생
recursive(numbers , 4 , 1 , 0 + 4[numbers의 0인덱스의 값]) ; //더하기 버전
recursive(numbers , 4 , 1 , 0 - 4[numbers의 0인덱스의 값]) ; //빼기 버전

recursive-1 일 때 (numbers, 4 , 1 , 4) 라고 가정하고 또 로직을 실행해보자.

recursive(numbers , 4 , 1 , 4 + 1[numbers의 1인덱스의 값]); //더하기 버전
recursive(numbers , 4 , 1 , 4 - 1[numbers의 1인덱스의 값]); //빼기 버전

...

이런식으로 반복적으로 호출이 되면서 주어진 배열의 값이 모두 연산에 사용되고
( index == numbers.length )
동시에 현재 now의 값이 target 과 일치한다면 인스턴스 변수의 count를 1 증가시킨다.
( now == target )

재귀를 이용한 풀이 (지역변수 레벨로 풀기)

인스턴스 변수가 아니라 지역 변수 레벨로 문제가 풀이되도록 다음과 같이 소스를 수정했다.

class Solution {    
    
    public int solution(int[] numbers, int target) {        
        return recursive(numbers , target , 0 , 0);        
    }     
    
    public int recursive(int[] numbers , int target , int index , int now) {
        
        if(index == numbers.length) {
            return now == target ? 1 : 0 ; //일치하면 1 반환 , 아니면 0 반환 
        }         
        return recursive(numbers, target , index+1 , now + numbers[index]) + 
               recursive(numbers, target , index+1 , now - numbers[index]);         }
}

실행결과

DFS 소스로 풀이

사실상 재귀랑 거의 흡사하다.

  public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private int dfs(int[] numbers, int target, int index, int currentSum) {
        if (index == numbers.length) {
            return currentSum == target ? 1 : 0;
        }
        
        // 현재 숫자를 더하는 경우
        int add = dfs(numbers, target, index + 1, currentSum + numbers[index]);
        // 현재 숫자를 빼는 경우
        int subtract = dfs(numbers, target, index + 1, currentSum - numbers[index]);
        
        // 두 가지 경우의 수를 합산
        return add + subtract;
    }

새롭게 알게된 점

기존 지식으로 풀이

다음에 풀어볼 문제 - ??

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL