• 티스토리 홈
  • 프로필사진
    유니얼
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
유니얼
  • 프로필사진
    유니얼
    • 분류 전체보기 (295)
      • Unity (17)
        • 게임 개발 (5)
      • Unreal (24)
        • 게임 개발 (20)
      • DirectX (36)
      • 코딩테스트 (91)
        • 프로그래머스 (25)
        • 백준 (66)
      • Google Workspace (1)
      • Programing (102)
        • C# (68)
        • C++ (24)
        • JavaScript (10)
      • 게임 서버 프로그래밍 (17)
      • Web (6)
        • 슈퍼코딩 (6)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
    등록된 댓글이 없습니다.
  • 최근 공지
    등록된 공지가 없습니다.
# Home
# 공지사항
#
# 태그
# 검색결과
# 방명록
  • [프로그래머스] 타겟 넘버(C++)
    2024년 01월 19일
    • 유니얼
    • 작성자
    • 2024.01.19.:30
    728x90

    안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "타겟 넘버" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 것이 목표입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

    문제링크 : 

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

     

    프로그래머스

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

    programmers.co.kr

    Question_1

    문제 개요

    "타겟 넘버" 문제는 주어진 숫자들을 더하거나 빼서 특정한 숫자(타겟 넘버)를 만드는 방법의 수를 찾는 문제입니다. 예를 들어, 숫자들 [1, 1, 1, 1, 1]과 타겟 넘버 3을 사용할 때, 가능한 조합은 5가지입니다.

    문제 해결 전략

    이 문제의 핵심은 모든 가능한 덧셈과 뺄셈의 조합을 탐색하는 것입니다. 이를 위해 깊이 우선 탐색(DFS) 알고리즘을 사용합니다. DFS는 각 숫자에 대해 더하거나 빼는 모든 경우를 탐색하며, 타겟 넘버에 도달할 때마다 카운터를 증가시킵니다.

    코드 구현

    #include <string>
    #include <vector>
    #include <bits/stdc++.h>
    using namespace std;
    
    // DFS 함수는 깊이 우선 탐색을 이용하여 문제를 해결합니다.
    // numbers: 사용할 숫자들이 담긴 배열
    // curIndex: 현재 처리 중인 numbers 배열의 인덱스
    // target: 만들고자 하는 타겟 넘버
    // sum: 현재까지의 누적 합계
    // count: 타겟 넘버를 만드는 방법의 수를 카운트하는 변수
    void DFS(vector<int> &numbers, int curIndex, int target, int sum, int &count) {
        // 모든 숫자를 고려했을 때,
        if (curIndex >= numbers.size()) {
            // 현재까지의 합계가 타겟 넘버와 동일한 경우, 카운트 증가
            if (sum == target) {
                count++;
                return;
            }
            return;
        }
        // 현재 숫자를 더하는 경우의 재귀 호출
        DFS(numbers, curIndex + 1, target, sum + numbers[curIndex], count);
        // 현재 숫자를 빼는 경우의 재귀 호출
        DFS(numbers, curIndex + 1, target, sum - numbers[curIndex], count);
    }
    
    // solution 함수는 주어진 문제를 해결하는 메인 함수입니다.
    // numbers: 사용할 숫자들이 담긴 배열
    // target: 만들고자 하는 타겟 넘버
    int solution(vector<int> numbers, int target) {
        int answer = 0; // 타겟 넘버를 만드는 방법의 수를 저장할 변수
        // DFS 함수를 호출하여 타겟 넘버를 만드는 모든 방법 탐색
        DFS(numbers, 0, target, 0, answer);
        return answer; // 결과 반환
    }

    코드 설명

    위 C++ 코드는 DFS를 사용하여 문제를 해결합니다. DFS 함수는 현재 인덱스(curIndex), 현재까지의 합(sum), 타겟 넘버(target), 그리고 가능한 조합의 수를 저장하는 count를 매개변수로 받습니다. 배열의 모든 요소를 고려할 때까지 재귀적으로 함수를 호출하며, 각 단계에서 현재 숫자를 더하거나 뺍니다. 만약 모든 숫자를 사용한 후 총합이 타겟 넘버와 일치하면 count를 증가시킵니다.

    결론

    이 "타겟 넘버" 문제는 깊이 우선 탐색을 사용하여 효과적으로 해결할 수 있습니다. 이 방법은 모든 가능한 조합을 체계적으로 탐색하면서, 주어진 조건에 부합하는 모든 경우의 수를 찾아냅니다. 이 접근 방식은 다양한 알고리즘 문제에 적용될 수 있으며, 특히 조합적 문제 해결에 유용합니다.

    반응형
    다음글
    다음 글이 없습니다.
    이전글
    이전 글이 없습니다.
    댓글
조회된 결과가 없습니다.
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
목차
표시할 목차가 없습니다.
    • 안녕하세요
    • 감사해요
    • 잘있어요

    티스토리툴바