주제 - “알고리즘 (DFS/BFS) - 1”
부제 - 프로그래머스 코딩테스트 연습 - 파이썬
출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 타겟 넘버
- 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.
문제 1. 타겟 넘버
[문제 설명]
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 이하인 자연수입니다.
[입출력 예]
| numbers | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
풀이
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
풀이의 포인트
numbers 리스트에 있는 숫자를 +, - 연산을 이용하여 적절히 조합, target 값을 만들어내는 방법의 개수를 확인하는 문제입니다.
즉, numbers = [a, b, c, d, e] 일 때 +, - 를 적절히 배치하여 아래의 식이 성립되는 경우의 수를 구하는 것입니다.
± a ± b ± c ± d ± e = target
1) 문제 파악하기 : DFS
± a ± b ± c ± d ± e = target 이어야 하므로, target ± a ± b ± c ± d ± e = 0 이라고 할 수 있습니다.
numbers의 각 숫자를 +, - 하는 것을 각 노드라고 했을 때, 아래와 같이 이진 트리를 그려 볼 수 있습니다.
문제를 해결하기 위해서는 target → ±a → ±b → ±c → ±d → ±e 순으로 탐색해야 합니다.
즉, numbers 리스트의 인덱스(-1) 를 높이로 하는 트리를 DFS로 탐색해야 하는 것입니다.
그리고 탐색하는 모든 경우의 수 중, 그 계산값이 0이 되는 경우의 수를 찾아내는 것이 목표에 해당됩니다. 따라서 탐색의 종료조건을 계산값이 0이 되는 경우로 지정해야 합니다.
여기까지 문제 파악을 마치고, 위의 DFS를 구현하기 위한 코딩을 시작합니다.
2) DFS 구현하기 (재귀)
DFS는 쭉 이어서 탐색하기 때문에 흔히 재귀를 사용하여 구현합니다. 이를 구현하기 위해서는 종료 조건과 재귀로 호출할 형태를 구성해야 합니다.
이 문제에서는 numbers 리스트에서 순서대로 값을 불러와 아래와 같이 ± 연산을 수행해야 합니다.
- target ± a
- (target ± a) ± b → A ± b
- (A ± b) ± c → B ± c
따라서 재귀되는 식은 X ± Y 의 형태이며, X는 target부터 계속 연산되어 온 값이고 Y는 numbers에서 하나씩 뽑아서 연산할 값입니다. 이는 곧 solution의 인자에 대응되어 들어갈 수 있습니다. solution(Y, X)의 형태인 셈입니다.
처음 연산이 시작되는 값은 target ± a 이므로, 이 둘로 재귀의 호출을 시작합니다. 이 둘로 뻗어나가는 경우의 수는 최종적으로 모두 합산되어야 하므로 +로 연결합니다. 그리고 그 다음으로 numbers에서 뽑힐 값은 그 다음 인덱스로 계속 이어져야 하므로, 아래와 같이 표현할 수 있습니다.
def solution(numbers, target):
return solution(numbers[1:], target + numbers[0]) + solution(numbers[1:], target - numbers[0])
위의 식을 통해 재귀로 함수를 수행하다가 numbers 리스트에서 모든 값을 뽑아냈다면, 재귀가 종료되어야 합니다. 종료 시 함수의 리턴값은 문제에서 요구한 대로 조건에 맞는 경우의 수여야 합니다. 현재는 재귀로 함수를 구현하므로, 해당 연산이 경우의 수를 만족하는지 여부에 따라 1 또는 0의 값을 리턴하여 더해나가야 합니다.
재귀의 종료조건은 numbers에 값이 존재하지 않는 경우(if not numbers)입니다. 최종 연산값이 0이면 경우의 수를 만족한 것이므로 1을, 그렇지 않다면 0을 리턴합니다.
따라서 최종적으로 아래와 같은 풀이가 완성됩니다.
def solution(numbers, target):
if not numbers and target == 0:
return 1
elif not numbers:
return 0
return solution(numbers[1:], target + numbers[0]) + solution(numbers[1:], target - numbers[0])