99클럽 코테 스터디 11일차 TIL - DFS, 재귀

오늘의 학습 키워드

DFS, 재귀

---

알고리즘 문제

• 프로그래머스 Level 2. 타겟 넘버
• https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

공부한 내용

DFS, 재귀

• 10일차(소수찾기 문제)에는 재귀를 활용해 순서를 바꿔가며 모든 숫자를 조합해야 했다.
• 이번 문제는 앞에서부터 하나의 숫자를 픽스 + 픽스한 숫자에 대한 경우는 2가지(+, -)가 있다.
• 그리고 픽스한 숫자의 인덱스의 바로 다음번째 인덱스의 숫자를 픽하게 되는데 이 때 또한 +, - 하는 경우의 수가 2개.
• 인덱스마다 순서대로 반복해서 2가지 경우(더하거나 빼거나)를 반복해서 주어진 배열 끝까지 돌아 합을 구하는 것.

---

오늘의 회고

처음 시도

• [4, 2, 1, 2] 케이스를 보면서 공책에 끄적여 봤다.

 

해결

• 앞에서부터 하나의 숫자를 픽스 => 픽스한 숫자에 대한 경우는 각각 2가지(+, -)가 있다.
• 순서대로 픽스한 숫자의 인덱스의 바로 다음번 인덱스의 숫자를 픽하게 되는데 이 때 또한 +, - 하는 경우의 수가 2개.
• 인덱스마다 순서대로 반복해서 2가지 경우(더하거나 빼거나)를 반복해서 주어진 배열 끝까지 돌아 합을 구하는 것.

---

문제 풀이

• 메모리 상 이득을 위해 자주 사용하게 될 변수는 따로 빼서 클래스 전체에서 사용할 수 있도록 선언해주었다.
  • count : sum이 target과 같은 모든 경우의 수
  • target: 주어진 변수 (target)
  • numbers: 주어진 변수 (numbers)
  • len: numbers.length
• dfs(0, 0) 은 처음에 재귀 호출할 때 인덱스가 0이고, sum을 0으로 시작한다.
• 재귀 종료 조건은 인덱스가 마지막까지 모두 돌은 경우(numbers의 길이만큼 돈 경우)
• 카운트 추가 조건은 인덱스가 마지막까지 모두 돌아서 합한 결과가 target가 같은 경우
• 재귀 호출 조건은 인덱스+1, 현재까지 결과에 + 다음 숫자 / 현재까지 결과에 - 다음 숫자

class Solution {
    int count;
    int target;
    int[] numbers;
    int len;
    
    public void dfs(int idx, int sum) {
        if (idx == len) {
        	if (sum == target) count++;
            return;
        }
        
        dfs(idx+1, sum + numbers[idx]);
        dfs(idx+1, sum - numbers[idx]); 
    }
    
    public int solution(int[] numbers, int target) {
        this.target = target;
        this.numbers = numbers;
        this.count = 0;
        this.len = numbers.length;
        
        dfs(0, 0);
        
        return count;
    }
}