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 를 사용하는 경우를 분리할 것 |
'CS > 알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스/알고kit/해시] 폰켓몬 (1) | 2024.03.07 |
---|---|
[BOJ23971/Python] ZOAC 4 (2) | 2024.03.05 |
[프로그래머스/알고kit/그리디] 체육복 (0) | 2024.01.21 |
[프로그래머스/알고kit/정렬] K번째수 (0) | 2024.01.18 |
[프로그래머스/알고kit/해시] 완주하지 못한 선수 (0) | 2024.01.18 |