[Algorithm] 타겟 넘버 - 프로그래머스 Lv.2

[ 코딩테스트 연습 - 프로그래머스 Lv.2 ]

• 문제명 : 타겟 넘버 [깊이/너비 우선탐색(DFS/BFS)]
• 사용 언어 : Python3
• 사용 알고리즘 : DFS (깊이 우선 탐색)

이 문제는 가능한 모든 경우의 수를 탐색해야 하므로, DFS(깊이 우선 탐색)을 사용하는 것이 적절하다.

DFS를 통해 가능한 모든 순열을 생성하고,

각 순열에 대해 주어진 규칙에 따라 타겟 넘버를 만들 수 있는지 확인하는 방식으로 접근할 수 있다.

DFS는 모든 경우의 수를 확인하는데에 유용하며, 이 문제에서도 모든 가능한 더하고 빼는 경우를 탐색할 수 있다.

 

---

문제 설명

 

 

 

▽ 문제 해결방법 설계 및 코드작성.

   : DFS를 사용하여 가능한 모든 경우를 탐색하는 방법을 선택.

   : 재귀 함수를 통해 모든 순열을 생성하면서 각각의 경우에 대해 덧셈과 뺄셈을 수행하여 'target'을 만들 수 있는지 확인.

   : 재귀 함수를 이용하여 DFS를 구현하고, 각 경우에 대해 'target'을 만들 수 있는지 확인하는 로직을 추가.

 

 

 

1. 기본 케이스 정의하기 ( 탈출조건 정의)

def dfs(index, current_sum):
    # 기본 케이스: 모든 원소를 확인한 경우
    if index == len(numbers):
        # 타겟 넘버를 만들면 1을 반환, 아니면 0 반환
        return 1 if current_sum == targer else 0

 

2. 현재 상태에서 가능한 다음 단계 정의하기

# 다음 단계: 현재 숫자를 더하거나 빼는 경우를 탐색
return dfs(index + 1, current_sum + numbers[index]) + dfs(index + 1, current_sum - numbers[index])

 

3. 입력 매개변수 처리하기

    - index : 현재 인덱스

    - current_sum : 현재까지의 합

 

4. 결과 반환하기

# 각각ㄱ의 재귀 호출이 기여한 결과를 합산하여 반환.
return dfs(index+1, current_sum + numbers[index]) + dfs(index+1, current_sum - numbers[index])

 

5. 전체 함수 구현

def solution(numbers, target):
    def dfs(index, current_sum):
        # 기본 케이스: 모든 원소를 확인한 경우
        if index == len(numbers):
            # 타겟 넘버를 만들면 1을 반환, 아니면 0 반환
            return 1 if current_sum == target else 0
        
        # 다음 단계: 현재 숫자를 더하거나 빼는 경우를 탐색
        return dfs(index+1, current_sum + numbers[index]) + dfs(index+1, current_sum - numbers[index])
        
    # 초기 인덱스 0부터 시작
    return dfs(0,0)

 

 

▽ 결과 확인 ▽