[프로그래머스/알고kit/DFS,BFS] 타겟 넘버

240127

---

문제

• n개의 음이 아닌 정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버 만들기
• 숫자가 담긴 배열 numbers, 타겟 넘버 target

---

문제 풀이 아이디어

• DFS 로 접근
• idx번째 operator 를 고르면서 check_num 으로 만든 숫자가 target 과 일치하는지 확인

def solution(numbers, target):
    def solve(idx, check_num):
        nonlocal answer
        if idx == N:
            if check_num == target:
                answer += 1
            return answer
            return
        elif idx < N:
            for operator in operators:
                if operator == '+':
                    solve(idx+1, check_num + numbers[idx])
                if operator == '-':
                    solve(idx+1, check_num - numbers[idx])
    # 사용할 변수들 선언
    operators = ['+','-'] # operator 를 나열
    N = len(numbers) # 전체 사용할 총 숫자의 개수
    answer = 0 # 전체 방법의 수 구하는 변수
    # 타겟 넘버를 만드는 방법의 수 return
    solve(0, 0) # idx, check_num
    return answer

---

Keep                                   Problem                                                         Try

(1) DFS 전략 (2) 재귀 함수를 이용하여 각 단계에서 숫자 +/- 경우 고려

(1) 모든 숫자를 사용해야 한다고 문제를 잘못 이해했음 (2) 부호를 다 골랐을 때 check_num 이 target과 맞는지 확인해야 하는데 그 전에도 확인하도록 했었음 (3) idx < N 일 때 종료return 되도록 해서 함수가 깊게 모든 경우를 탐색하지 못했음 (4) '-' 로 넘어가는 경우를 elif 로 선언해서 처음 부호가 마이너스인 경우를 생각하지 못했음

(1) 문제를 파악할 때 모든 숫자를 사용해야만 하는 조건이 있다고 머릿속으로 생각했었는데 그게 아니었음 ! 써있는대로의 조건만 접근할 것 (2) 함수 내부에서 종료 조건과 반환값을 마구 바꾸지 말고 키보드에서 손을 떼고 손으로 종이에 그려보면서 생각해보는 게 오히려 빠른 길 (3) 재귀 함수의 구조 개선 : if - if 와 if - elif 를 사용하는 경우를 분리할 것