페블_
반짝이는 시냅스
페블_
전체 방문자
오늘
어제
  • 전체글 보기 (96)
    • QA (0)
    • 프로젝트 회고 (4)
    • 프로젝트 과정 기록 (12)
    • UI 구현 연구일지 (8)
    • Front-end (31)
      • Javascript (7)
      • CSS (10)
      • React (5)
      • Typescript (3)
      • Nextjs (3)
      • 스타일링 라이브러리 (3)
    • Back-end (0)
      • Express (0)
      • DB (0)
    • CS (0)
      • 자료구조 & 알고리즘 (0)
    • CI&CD (1)
    • 툴 사용법 (4)
      • Git (1)
      • Library&패키지 (2)
      • 기타 개발관련 (1)
    • 알고리즘 이론 & 풀이 (36)
      • 백준(BOJ) (14)
      • 프로그래머스 (22)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Python
  • 생각
  • 백준
  • emotion
  • 캐러셀
  • TypeScript
  • storybook
  • eslint
  • chartjs
  • 개발블로그_시작
  • 토이프로젝트
  • 시리즈_표지
  • react
  • JS
  • 선형대수학
  • 알고리즘
  • UI 컴포넌트
  • 파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
페블_

반짝이는 시냅스

알고리즘 이론 & 풀이/프로그래머스

프로그래머스 Lv.2 | (DFS) 타겟 넘버 js

2023. 8. 9. 01:34

문제

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

 

풀이

  • 모든 가능한 조합을 시도해봐야 한다. numbers 배열의 숫자를 순서대로 + 혹은 -를 해봐야 한다. 마치 각 숫자 노드에 다음 숫자가 +, - 두 가지 버전으로 달려있는 이진트리를 모두 순회하는 경우와 같다.
  1. 깊이 우선 탐색(DFS) 이므로 dfs라고 함수를 만들고, 다음 인덱스로 넘어가기 위한 index, 합을 축적할 currSum을 마련한다.
  2. 인덱스와 sum은 0부터 시작하므로 처음에는 dfs(0, 0)로 시작한다.
  3. dfs의 종료 조건은 index가 numbers.length가 될 때 (배열의 인덱스 범위보다 넘쳤을 때)이다. 이때는 여태가지 축적한 sum이 target과 같은지 검사하고, 맞다면 count++ 해준다.
  4. dfs 재귀호출에서 인덱스 파라미터는 index + 1로 다음 인자를 호출하고, sum은 sum에 숫자를 더하거나 뺀 두 가지 버전을 준비한다.
  5. dfs 호출이 모두 끝났으면 count를 반환한다.
function solution(numbers, target) {
    let count = 0;
    function dfs(index, currSum) {
        if(index === numbers.length) {
            if(currSum === target) count++;
            return;
        }
        
        dfs(index + 1, currSum + numbers[index]);
        dfs(index + 1, currSum - numbers[index]);
    }
    
    dfs(0, 0);
    return count;
}

'알고리즘 이론 & 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스 Lv.2 | (스택/큐) 기능개발 js  (0) 2023.08.09
프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js  (0) 2023.08.09
프로그래머스 Lv.1 | (완전탐색) 모의고사 js  (0) 2023.08.09
프로그래머스 Lv.2 | (완전탐색) 소수찾기 js  (0) 2023.08.08
프로그래머스 Lv.1 | 전화번호 목록 js  (0) 2023.08.08
    '알고리즘 이론 & 풀이/프로그래머스' 카테고리의 다른 글
    • 프로그래머스 Lv.2 | (스택/큐) 기능개발 js
    • 프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js
    • 프로그래머스 Lv.1 | (완전탐색) 모의고사 js
    • 프로그래머스 Lv.2 | (완전탐색) 소수찾기 js
    페블_
    페블_

    티스토리툴바