문제
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
예제
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4- 총 2가지 방법이 있으므로, 2를 return 합니다.
나의 풀이 (DFS, 재귀함수)
def solution(nums, target):
cnt = 0
def dfs(i, res):
if i == len(nums):
if res == target:
nonlocal cnt
cnt += 1
return
for op in ["+", "-"]:
if op == "+":
res += nums[i]
dfs(i+1, res)
res -= nums[i]
else:
res -= nums[i]
dfs(i+1, res)
dfs(0, 0)
return cnt- 백트래킹 알고리즘을 이용해서 DFS로 탐색하는 방법으로 풀었다.
- for문을 이용해 리스트의 각 인덱스마다 각각 수를 더하고 뺀다.
- 플러스를 한 후에는 마이너스 계산을 위해
res -= nums[i]를 실행해 더하기 이전의 값으로 돌려놓는 절차가 필요하다.
- 플러스를 한 후에는 마이너스 계산을 위해
nums의 인덱스를 넘어서면(더이상 더하거나 뺄 수가 없을때) 재귀함수를 종료한다.- 백준에서 문제 푸는 것에 익숙해서
global cnt로 작성했다가NameError가 발생했다.cnt가solution()함수 내부에 정의되었기 때문에nonlocal를 사용해야 한다.
다른 사람의 풀이1 (DFS - 재귀함수)
def dfs(nums, target, i, res):
global cnt
if i == len(nums):
if res == target:
return 1
else:
return 0
return dfs(nums, target, i+1, res+nums[i]) + dfs(nums, target, i+1, res-nums[i])
def solution(nums, target):
return dfs(nums, target, 0, 0)- 카운트 변수를 따로 선언하지 않고 타겟 넘버 달성 여부에 따른
dfs()함수의 출력값을 모두 더하면 경우의 수를 출력할 수 있다. - 좀 더 재귀함수의 정석에 가까운 풀이방법인 거 같다.
- 플러스 마이너스를 for문이 아닌 각각의 함수로 실행하니까 더한 값을 다시 빼는 과정이 빠져서 더욱 깔끔한 코드가 됐다.
다른 사람의 풀이2 (BFS - 큐)
from collections import deque
def solution(nums, target):
queue = deque([(0, 0)]) # (현재 인덱스, 현재 합)
cnt = 0
while queue:
index, res = queue.popleft()
if index == len(nums):
if res == target:
cnt += 1
else:
queue.append((index+1, res+nums[index]))
queue.append((index+1, res-nums[index]))
return cnt- 큐에 각 요소를 튜플 형태(현재 인덱스, 현재 합)로 저장한다.
- 값을 더하거나 빼면서 큐의 요소를 계속 늘려나가다가, 인덱스가
len(nums)에 도달하면 그때부먼 튜플을 하나씩 제거하면서 숫자의 합이 타겟에 도달했는지 여부를 판단하고, 모든 요소를 제거하면 while문을 종료한다.
다른 사람의 풀이3 (BFS)
def solution(nums, target):
leaves = [0] # 모든 계산 결과를 담음
cnt = 0
for num in nums:
temp = []
for leaf in leaves:
temp.append(leaf + num)
temp.append(leaf - num)
leaves = temp
for leaf in leaves:
if leaf == target:
cnt += 1
return cntleaves에 이전 수에 플러스, 마이너스한 결괏값을 담는다.
회고
- 문제를 읽자마자 어떤 알고리즘으로 어떻게 풀어야 할지 머릿속에 쫙 펼쳐지는 놀라운 경험을 했다.
- 며칠 동안 머리 싸매면서 열심히 알고리즘 공부했더니 조금씩 결과가 보이는 것 같아서 뿌듯하다.
- 다른 사람들 풀이까지 확인하면서 알고리즘 풀이 방법이 참 무궁무진하다는 걸 새삼 깨달았다.