작성일 : 2024.11.04

타겟 넘버 문제

문제 설명

n개의 음이 아닌 정수로 이루어진 수열이 주어졌을 때, 숫자들을 순서대로 더하거나 빼서 타겟 넘버를 만드는 모든 방법의 수를 구하는 문제입니다.

예시

numbers = [1, 1, 1, 1, 1], target = 3인 경우의 방법들:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

총 5가지 방법이 있습니다.

제한 조건

1. numbers 배열 제한

   • 숫자 개수: 2개 이상 20개 이하
   • 각 숫자의 범위: 1 이상 50 이하의 자연수

2. target 제한

   • 범위: 1 이상 1000 이하의 자연수

해결 코드

function solution(numbers, target) {
  let answer = 0;
  const dfs = (num, index) => {
    if (index == numbers.length) {
      if (num == target) answer++;
      return;
    }
    dfs(num + numbers[index], index + 1);
    dfs(num - numbers[index], index + 1);
  };
  dfs(0, 0);
  return answer;
}

알고리즘 설명

이 문제는 DFS(깊이 우선 탐색)를 사용하여 해결합니다:

1. DFS 함수 정의

   • 매개변수
     • num: 현재까지의 계산 결과
     • index: 현재 처리 중인 숫자의 인덱스

2. 종료 조건

   • index가 numbers 배열의 길이와 같아졌을 때
   • 현재까지의 계산 결과(num)가 target과 같으면 answer 증가

3. 재귀 호출

   • 현재 숫자를 더하는 경우와 빼는 경우 두 가지로 분기
   • 각각의 경우에 대해 다음 인덱스로 재귀 호출

핵심 문법 요소

1. 화살표 함수를 이용한 DFS 구현

const dfs = (num, index) => {
  // 함수 내용
};

2. 재귀 호출을 통한 모든 경우의 수 탐색

dfs(num + numbers[index], index + 1);
dfs(num - numbers[index], index + 1);

3. 조건문을 통한 목표값 도달 확인

if (num == target) answer++;

시간 복잡도

• O(2^n): 각 숫자마다 더하기/빼기 두 가지 경우를 고려
• n은 numbers 배열의 길이

공간 복잡도

• O(n): 재귀 호출로 인한 콜 스택 사용
• n은 numbers 배열의 길이