[프로그래머스] 타겟 넘버
🔒 문제 분석
알겠지만 easy 수준의 문제는 문제 분석 능력을 따로 필요로 하지 않는다. '알고리즘' 보단 어떤 '자료구조'를 쓸지만 떠올리면 되지만, 레벨 2 이상을 올라가면 자료구조, 알고리즘 모두 고려를 해야 하는 상황이기 때문에 문제 분석을 해야한다.
1. 모든 조합을 탐색해야 하는 상황
- 주어진 숫자들을 가지고 더하거나 빼서 타겟 넘버를 만들어야 한다.
- 각 숫자에 대해 - ,+ 의 옵션이 있으므로 이를 통해 가능한 모든 조합을 탐색 해야한다.
- "모든 조합을 탐색"해야 하는 문제는 보통 DFS나 BFS로 접근한다.
2. 재귀적 구조
- 각 숫자에 대해 두가지 선택지를 고려해야 하는데, 이는 재귀적으로 각 선택지를 탐색하는 구조와 유사하다.
- 특히, 특정 조건을 만족하는 모든 경로를 찾거나 모든 가능한 경로를 탐색하는 문제는 DFS로 해결하는 경우가 많다.
3. 문제의 조건
- 주어진 숫자들의 순서를 바꾸지 않고 각 숫자를 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 찾아야 한다.
- 이는 각 단계마다 두 가지 선택지를 가지는 트리 구조로 생각할 수 있습니다. DFS는 트리의 모든 경로를 탐색하는 데 적합하다.
이러한 문제를 보고 DFS를 떠올리게 되는 핵심 포인트는:
- 모든 가능한 조합을 탐색해야 하는 요구사항
- 재귀적 탐색이 필요함
- 경로의 누적 합을 관리해야 함
DFS는 두 가지 방식으로 구현될 수 있다:
- 재귀 호출을 통한 구현
- 스택을 이용한 반복적 구현
재귀 호출 방식이 더 직관적이고 간단하기 때문에 많이 사용된다. 하지만 재귀 깊이가 깊어질 경우 스택 오버플로우 문제가 발생할 수 있으며, 이럴 때는 반복적 구현이 유용할 수 있다.
def solution(numbers, target):
def dfs(index, current_sum):
if index == len(numbers):
return 1 if current_sum == target else 0
add_case = dfs(index + 1, current_sum + numbers[index])
subtract_case = dfs(index + 1, current_sum - numbers[index])
return add_case + subtract_case
return dfs(0, 0)
- 재귀적으로 호출할 dfs라는 함수를 선언 해준다. 우리가 필요한것은 target에 도달했는지 확인을 하기 위한 current_sum과 index를 파라미터로 받는다.
- 이 함수가 호출되면, 먼저 파라미터로 받은 인덱스가 현재 입력값으로 받은 numbers의 길이와 일치하는지 확인한 후(리스트에 끝에 도달했음을 의미), 만약 현재 리스트 끝에 도달했고, current_sum이 target과 일치한다면 1을 반환하고, 그렇지 않다면 0을 반환한다. 여기서 1을 반환하는건 경우의 수 카운트 +1 이라고 생각하면 쉽다.
-다음으로, 2가지의 케이스(+, -)를 담당할 재귀문을 작성 해준다.
- add_case는 다음 인덱스와 현재까지의 합에서 현재 검사중인 요소를 '더해' 재귀문을 호출한다.
- subtract_case는 다음 인덱스와 현재까지의 합에서 현재 검사중인 요소를 '빼서' 재귀문을 호출한다.
🔍 재귀...백트래킹... 하아
글을 쓰다 보니 작년 자구알고 수업때 재귀를 공부하다가 고통받았던 기억이 나 다시 한번 재귀 + 백트래킹을 좀 더 자세히 살펴보고 넘어 가보자.
재귀 함수 호출은 실제로 함수 호출 스택에 쌓인다. 각 재귀 호출은 함수 호출 스택에 새로운 프레임을 추가하고, 해당 호출이 완료되면 스택에서 제거(pop)된다. 이 과정은 재귀 호출이 진행되는 동안 함수 호출 순서와 현재 상태를 관리하는 데 사용된다.
재귀 함수의 스택 동작
예를 들어, `numbers = [1, 1, 1, 1, 1]`이고 `target = 3`인 경우를 다시 살펴보자.
재귀 호출 순서와 스택 동작
1. 초기 호출: `dfs(0, 0)` 호출:
- `index = 0`, `curr_sum = 0`
- 호출 스택: `[dfs(0, 0)]`
2. 첫 번째 숫자에 대해:
- `add_case = dfs(1, 1)` 호출:
- `index = 1`, `curr_sum = 1`
- 호출 스택: `[dfs(0, 0), dfs(1, 1)]`
3. 두 번째 숫자에 대해:
- `add_case = dfs(2, 2)` 호출:
- `index = 2`, `curr_sum = 2`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2)]`
4. 세 번째 숫자에 대해:
- `add_case = dfs(3, 3)` 호출:
- `index = 3`, `curr_sum = 3`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3)]`
5. 네 번째 숫자에 대해:
- `add_case = dfs(4, 4)` 호출:
- `index = 4`, `curr_sum = 4`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 4)]`
6. 다섯 번째 숫자에 대해:
- `add_case = dfs(5, 5)` 호출:
- `index = 5`, `curr_sum = 5`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 4), dfs(5, 5)]`
- 조건 `index == len(numbers)`이 참이므로, `curr_sum == target`를 확인하고, `0`을 반환.
- 스택에서 `dfs(5, 5)`가 제거되고, `dfs(4, 4)`로 돌아감.
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 4)]`
7. 백트래킹:
- `dfs(4, 4)`에서 `subtract_case = dfs(5, 3)` 호출:
- `index = 5`, `curr_sum = 3`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 4), dfs(5, 3)]`
- 조건 `index == len(numbers)`이 참이므로, `curr_sum == target`를 확인하고, `1`을 반환.
- 스택에서 `dfs(5, 3)`가 제거되고, `dfs(4, 4)`로 돌아감.
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 4)]`
- `dfs(4, 4)`에서 `add_case + subtract_case = 0 + 1 = 1` 반환.
- 스택에서 `dfs(4, 4)`가 제거되고, `dfs(3, 3)`로 돌아감.
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3)]`
8. 세 번째 숫자에 대해:
- `dfs(3, 3)`에서 `subtract_case = dfs(4, 2)` 호출:
- `index = 4`, `curr_sum = 2`
- 호출 스택: `[dfs(0, 0), dfs(1, 1), dfs(2, 2), dfs(3, 3), dfs(4, 2)]`
이와 같은 방식으로 재귀 호출은 계속해서 스택에 쌓이고, 기저 조건에 도달하면 반환하면서 스택에서 제거된다.
요약
- 재귀 호출 스택: 각 함수 호출은 스택에 쌓인다. 재귀 호출이 반환될 때마다 스택에서 제거된다.
- 백트래킹: 한 경로의 탐색이 끝나면(재귀 호출이 반환되면) 스택에서 제거되고, 이전 호출로 돌아가서 다음 경로를 탐색한다.
- 함수 호출 순서: 각 함수 호출은 순차적으로 진행되며, 호출이 완료되면 스택에서 제거되고, 다음 경로를 탐색하기 위해 이전 상태로 돌아간다.