[프로그래머스] 타겟 넘버

2024. 10. 12. 11:16·PS

 

 


 

문제

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

개념

DFS

 

 

실행 결과

 

 

 

 

구현 코드(JavaScript)

function solution(numbers, target) {
  function dfs(index, sum) {
    // 다 돌았을 때 합이 target과 같으면 1, 아니면 0을 반환
    if (index === numbers.length) {
      return sum === target ? 1 : 0;
    }
    
    const plus = dfs(index + 1, sum + numbers[index]);
    const minus = dfs(index + 1, sum - numbers[index]);

    return plus + minus;
  }

  return dfs(0, 0);
}

 

 

 

 

코드 설명

먼저 이 문제는 DFS(깊이 우선 탐색) 알고리즘으로 접근해야 한다.

 

DFS를 사용해야 하는 이유?

numbers 내 모든 원소에 대해 +와 -를 적용하고

반복문을 돌면서 이 두 가지 경우에 대한 모든 합을 구해야 한다.

그리고 반복문을 다 돌았을 때 이 합이 target과 일치하면 일치한 횟수를 리턴한다.

여기서 모든 경우를 더하기 위해 재귀를 사용하여 탐색하는 것이다.

 

plus를 사용해 +, minus를 사용해 각각 dfs를 진행한다.

만약 합이 타겟 넘버와 일치하면 일치하는 만큼 각 변수의 값이 +1된다.

재귀를 돌아 타켓넘버와 일치하는 합이 나올때마다 자동으로 값을 더해주기 때문에 

따로 카운트용 변수를 정의하지 않아도 코드가 잘 돌아간다.

 

 

 


 

저작자표시 (새창열림)

'PS' 카테고리의 다른 글

[백준] 1010번: 다리 놓기  (0) 2024.10.23
[백준] Fly me to the Alpha Centauri  (0) 2024.10.17
[프로그래머스] 문자열 여러 번 뒤집기  (0) 2024.10.10
[프로그래머스] 주사위 게임 3  (2) 2024.10.09
[백준] 10830번: 행렬 제곱  (0) 2024.10.08
'PS' 카테고리의 다른 글
  • [백준] 1010번: 다리 놓기
  • [백준] Fly me to the Alpha Centauri
  • [프로그래머스] 문자열 여러 번 뒤집기
  • [프로그래머스] 주사위 게임 3
abyss-s
abyss-s
프론트엔드 개발합니다!
  • abyss-s
    abyss-s의 블로그입니다.
    abyss-s
  • 전체
    오늘
    어제
    • 분류 전체보기 (192)
      • Web (16)
        • JavaScript (6)
        • TypeScript (1)
        • React (5)
        • Vue (0)
        • Storybook (1)
        • Next.js (1)
      • Backend & Infra (8)
        • Database (3)
        • Node.js (2)
        • SpringBoot (1)
      • PS (71)
      • CS (30)
        • OS (13)
        • Structure & Algorithm (5)
        • Network (10)
        • 정보처리기사 (2)
      • Language (18)
        • OOP (1)
        • JAVA (13)
        • C++ (4)
      • Activities (16)
        • 멋쟁이 사자처럼 (2)
        • OSSCA (3)
        • LG U+ URECA (5)
        • Project (2)
        • Conference (1)
      • IT (3)
      • AI (0)
      • Git & Github (5)
      • Notion (1)
      • Statistics (11)
      • Book (5)
      • Diary (1)
      • Game (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
    • 백준
    • 트위터
  • 공지사항

    • abyss-s의 티스토리에 오신 것을 환영합니다.
  • 인기 글

  • 태그

    백준
    통계학
    React
    그리디
    코드트리
    생활코딩
    자바스크립트
    자바기반응용프로그래밍
    파이썬
    OS
    DP
    JavaScript
    운영체제
    Java
    BFS
    네트워크
    Python
    BAEKJOON
    github
    C++
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
abyss-s
[프로그래머스] 타겟 넘버
상단으로

티스토리툴바