며칠 동안 하루에 평균 2문제씩 풀어 Level 1 수준의 문제는 모두 풀었다.
이제 본격적으로 Level 2 수준으로 난이도를 올려볼 것인데 BFS/DFS는 코딩 테스트에서 빈번하게 나오기 때문에 반드시 마스터해야 한다. 따라서 대부분의 해당 유형의 문제는 BFS로도 DFS로도 다 풀 수 있는데, 학습을 위해서 해당 카테고리의 문제는 두 가지 방법 모두 사용해서 풀어볼 예정이다.
풀이 - BFS 버전
먼저 BFS를 사용하여 풀어보자. 너비 우선 탐색이니 값이 주어지면 아래와 같이 다 탐색해 보는 것을 머릿속으로 상상할 수 있다.
그리고 원래 정석적인 그래프 구조에서의 BFS라면 visited 같은 것을 남겨서 재방문하지 않도록 표시를 해줘야 하는데 단순히 1차원 형태의 배열이 주어지니 이 부분은 생략할 수 있다.
# 첫번째
# [4], [-4]
# 두번째
# [4,1], [4,-1], [-4,1], [-4,-1]
# 세번째
# [4,1,2], [4,1,-2], [4,-1,2], [4,-1,-2],
# [-4,1,2], [-4,1,-2], [-4,-1,2], [-4,-1,-2]
# 네번째
# [4, 1, 2, 1], [4, 1, 2, -1], [4, 1, -2, 1], [4, 1, -2, -1],
# [4, -1, 2, 1], [4, -1, 2, -1], [4, -1, -2, 1], [4, -1, -2, -1],
# [-4, 1, 2, 1], [-4, 1, 2, -1], [-4, 1, -2, 1], [-4, 1, -2, -1],
# [-4, -1, 2, 1], [-4, -1, 2, -1], [-4, -1, -2, 1], [-4, -1, -2, -1]
BFS의 경우 큐 자료구조를 일반적으로 활용하는데, 파이썬에서는 collections 라이브러리에 포함되어 있는 deque 구조를 사용하여 동일하게 활용할 수 있다. 따라서 먼저 해당 라이브러리를 임포트하고 덱 자료구조를 하나 초기화해 주자.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
이제 덱 안에 뭘 넣을지부터 생각해야 한다. 4, -4 그리고 4+1, 4-1, -4+1, -4-1, ... 이런 식으로 진행할 것이니까 현재 합계를 저장해야 한다.
또한, 더하는 경우도 있고 빼는 경우도 있는데 인덱스를 덱 안에 포함시켜 [누적합, 인덱스]로 관리하면 편할 것 같다는 생각을 할 수 있다. (deque 자료 구조에 append를 할 때는 인자를 하나만 넣을 수 있으므로 d.append(0,0)과 같이 2개의 인자를 넣을 경우 에러가 뜬다.)
마지막으로 우리가 정답으로 반환해야 하는 경우는 모든 계산을 다 했을 경우, 타겟 값과 일치하는 개수를 반환해야 하므로 개수를 카운팅할 변수 cnt도 0으로 초기화하자.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
이제 while 문을 돌면서 큐 안에 더 이상 진행할 작업이 없을 때까지 반복하면 된다.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
while d:
반복문 안에서는 무슨 작업을 해야 할까?
처음 BFS 유형을 풀면 while문 안에 코드를 어떻게 짜야 할지 감을 잡기 어렵고 무엇부터 해야 하는지 정하는 게 가장 어려운 것 같다.
다시 앞으로 돌아가서, 가장 먼저 큐에서 누적합과 현재 인덱스를 pop하여 current라는 변수에 넣자.
그리고 현재의 누적합과, 현재의 인덱스도 저장해야 한다. 이 부분까지 코드를 작성해 보자.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
while d:
current = d.popleft()
current_sum = current[0] # d[0][0]
current_idx = current[1] # d[0][1]
이제 4, -4 그리고 4+1, 4-1, -4+1, -4-1, ... 이런 식으로 누적합을 구하고 인덱스를 증가시키는 코드를 작성해야 한다.
현재 인덱스에 해당하는 number를 누적합 변수에서 각각 더하거나 빼는 경우를 각각 큐에 추가해준다.
그리 현재 인덱스에서 1씩 증가시키는 부분을 포함해 주어야 한다.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
while d:
current = d.popleft()
current_sum = current[0] # d[0][0]
current_idx = current[1] # d[0][1]
d.append([current_sum + numbers[current_idx], idx+1])
d.append([current_sum - numbers[current_idx], idx+1])
여기까지 하면 4, -4, 4+1, 4-1, -4+1, -4-1, ... 이런 식으로 진행하는 코드는 작성되었다.
이제 타깃과 일치하는 경우를 카운트해야 하는데, 모든 번호까지의 연산이 끝났을 때, 타깃과 일치하는 경우를 세어야 한다.
즉, idx가 len(numbers) 값과 일치하는 경우이면서 current_sum이 target과 동일해야 한다.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
while d:
current = d.popleft()
current_sum = current[0] # d[0][0]
current_idx = current[1] # d[0][1]
d.append([current_sum + numbers[current_idx], idx+1])
d.append([current_sum - numbers[current_idx], idx+1])
if current_idx == len(numbers) and current_sum == target:
cnt += 1
이제 거의 정답에 도달했지만 해당 코드로 진행하면 IndexError: list index out of range 에러가 발생한다. 그 이유는 누적합을 계산할 때 누적합 연산마다 인덱스가 1씩 증가하는데, 어디까지 증가시킬 건지에 대한 조건이 없기 때문이다.
idx는 반드시 len(numbers)보다 작아야 하기 때문에 if문만 추가하면 정상적으로 문제를 해결할 수 있다.
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
d.append([0, 0]) # sum, index
cnt = 0
while d:
current = d.popleft()
current_sum = current[0] # d[0][0]
current_idx = current[1] # d[0][1]
if current_idx < len(numbers):
d.append([current_sum + numbers[current_idx], current_idx+1])
d.append([current_sum - numbers[current_idx], current_idx+1])
if current_idx == len(numbers) and current_sum == target:
cnt += 1
return cnt
풀이 - DFS 버전
다음으로는 DFS로 푸는 방법을 공유하고자 한다. DFS는 깊이 우선 탐색으로 다음과 같이 값을 더하거나 빼게 될 것이다.
# 첫번째
# [4], [-4]
# 두번째
# [4,1], [4,-1], [-4,1], [-4,-1]
# 세번째
# [4,1,2], [4,1,-2], [4,-1,2], [4,-1,-2],
# [-4,1,2], [-4,1,-2], [-4,-1,2], [-4,-1,-2]
# 네번째
# [4, 1, 2, 1], [4, 1, 2, -1], [4, 1, -2, 1], [4, 1, -2, -1],
# [4, -1, 2, 1], [4, -1, 2, -1], [4, -1, -2, 1], [4, -1, -2, -1],
# [-4, 1, 2, 1], [-4, 1, 2, -1], [-4, 1, -2, 1], [-4, 1, -2, -1],
# [-4, -1, 2, 1], [-4, -1, 2, -1], [-4, -1, -2, 1], [-4, -1, -2, -1]
DFS의 경우 보통 스택 자료구조나 재귀 함수를 이용하여 해결할 수 있는데, 필자는 재귀 함수를 사용하여 문제를 해결하였다.
재귀 함수를 통해 문제를 해결할 때는 기본적으로 재귀 함수의 틀을 작성해 놓고 풀면 편하다.
문제 풀이를 위해서 일단 재귀 함수를 호출할 때 어떤 인자를 넣어서 호출할 것인지, 반환값으로 무엇을 받을지 먼저 생각해 봐야 한다.
일단, 정답으로는 누적합과 타겟이 일치하는 개수를 반환해야 하므로 함수를 호출할 때 cnt = dfs()를 통해 총 개수를 반환받도록 세팅하였다.
다음으로 재귀 함수를 작성할 때는 반드시 재귀 탈출 조건을 작성해야 한다.
필자는 재귀 호출한 인덱스가 numbers의 개수와 일치한다면 종료하도록 설정하였다. 그렇다면 현재 인덱스에 대한 정보에 대해 재귀 함수가 알아야 하므로 인자값에 포함되어야 하고, 누적합 역시 포함되어야 한다.
따라서 dfs()라는 재귀 함수의 인자값으로는 현재 누적합과 현재 인덱스가 포함된 상태로 호출되어야 하므로 dfs(current_sum, current_idx)와 같이 호출할 수 있다. 지금까지 생각한 내용으로 기초적인 코드를 작성하면 아래와 같다.
def solution(numbers, target):
current_sum, current_idx = 0, 0
def dfs(current_sum, current_idx):
return 1 if current_idx == len(numbers) 0
cnt = dfs(current_sum, current_idx)
return cnt
다음으로는 4+1+2+1, 4+1+2-1, 4+1-2+1, 4+1-2-1, ... 이런 식으로 누적합을 계산하는 부분을 재귀 함수에서 나눠줘야 하는데, 더하는 부분과 빼주는 케이스로 나눠서 생각해볼 수 있다.
가장 처음에는 4에 대해서 4와 -4로 나눌 수 있고,
다음은 4+1, 4-1, -4+1, -4-1로 나눌 수 있다.
그리고 4+1+2, 4+1-2, 4-1+2, 4-1-2, -4+1+2, -4+1-2, -4-1+2, -4-1-2, ... 이와 같은 방식으로 계속 진행될 것이다.
따라서 재귀 함수에 누적합에 다음 값을 더하는 경우와 다음 값을 빼는 경우를 다음과 같이 작성할 수 있다.
def solution(numbers, target):
current_sum, current_idx = 0, 0
def dfs(current_sum, current_idx):
return 1 if current_idx == len(numbers) 0
add = dfs(current_sum + numbers[current_idx], current_idx+1)
sub = dfs(current_sum - numbers[current_idx], current_idx+1)
cnt = dfs(current_sum, current_idx)
return cnt
단, 두 경우 모두 인덱스는 하나씩 증가시켜야 한다.
이제 최종적으로 dfs는 타겟과 일치하는 개수를 반환해 줘야 하는데, 이를 위해 재귀 함수의 탈출 조건을 조금 수정해야 한다.
현재는 단순히 현재 인덱스 값과 numbers의 개수가 일치하면 return 하도록 작성되어 있는데, 기존의 조건문 안에 current_sum과 target이 일치하면 1을 반환하고 아니면 0을 반환하도록 수정하고, dfs() 재귀 함수에서는 각각 리턴 받은 개수의 합인 add + sub를 반환하도록 작성하면 최종적으로 문제를 해결할 수 있다.
def solution(numbers, target):
current_sum, current_idx = 0, 0
def dfs(current_sum, current_idx):
if current_idx == len(numbers):
return 1 if current_sum == target else 0
add = dfs(current_sum + numbers[current_idx], current_idx+1)
sub = dfs(current_sum - numbers[current_idx], current_idx+1)
return add + sub
cnt = dfs(current_sum, current_idx)
return cnt
문제 설명
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
[4, 1, 2, 1] 4 2
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.
최종 코드 - BFS 버전
from collections import deque
def solution(numbers, target):
d = deque() # for BFS
# [4], [-4]
# [4,1], [4,-1], [-4,1], [-4,-1]
# [4,1,2], [4,1,-2], [4,-1,2], [4,-1,-2]
# [4,1,2,1], [4,1,2,-1], [4,1,-2,1], [4,1,-2,-1]
d.append([0, 0]) # sum, index
cnt = 0
while d:
current = d.popleft()
current_sum = current[0] # d[0][0]
current_idx = current[1] # d[0][1]
if current_idx < len(numbers):
d.append([current_sum + numbers[current_idx], current_idx+1])
d.append([current_sum - numbers[current_idx], current_idx+1])
if current_idx == len(numbers) and current_sum == target:
cnt += 1
return cnt
최종 코드 - DFS 버전
def solution(numbers, target):
current_sum, current_idx = 0, 0
def dfs(current_sum, current_idx):
if current_idx == len(numbers):
return 1 if current_sum == target else 0
add = dfs(current_sum + numbers[current_idx], current_idx+1)
sub = dfs(current_sum - numbers[current_idx], current_idx+1)
return add + sub
cnt = dfs(current_sum, current_idx)
return cnt'LeetCode & Programmers' 카테고리의 다른 글
| [Programmers] 스택/큐 - 기능 개발 (0) | 2026.05.29 |
|---|---|
| [Programmers] 해시 - 전화번호 목록 (0) | 2026.05.29 |
| [Programmers] 완전 탐색 - 모의고사 (0) | 2026.05.29 |
| [Programmers] 완전 탐색 - 최소 직사각형 (0) | 2026.05.29 |
| [Programmers] 정렬 - K번째 수 (0) | 2026.05.29 |