[코테] 99클럽 코테 스터디 11일차 TIL - DFS/BFS (feat.재귀)
Question1 - [미들러] 타겟 넘버
문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/42839
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 이하인 자연수입니다.
문제풀이
trial1
우선 깊이 우선탐색 DFS나 재귀함수를 활용하지 않고 푼 방법으로,
itertools의 product를 활용해서 -1, 1로 이루어진 numbers 길이 만큼의 [-1,1,1,-1..] 식의 부호 리스트를 만든다.
그리고나서 부호 리스트의 각 인덱스별 요소와 numbers의 인덱스별 요소들을 곱한 합을 구하고,
그 합이 target의 값과 동일한지를 확인하면 된다.
정확도, 효율성 모두 통과하기는 했으나 DFS, 재귀함수를 쓰는게 아마도 더 효율적일 것으로 보인다.
def solution(numbers, target):
from itertools import product
count = 0
# 모든 숫자에 대해 +1, -1 두 가지 경우를 고려
signs = list(product([1, -1], repeat=len(numbers)))
# 모든 조합을 생성
for sign in signs:
current_sum = 0
for i in range(len(numbers)):
current_sum += sign[i] * numbers[i] # +1 혹은 -를 곱한 요소들의 전체 합
# 합이 target과 같으면 count 증가
if current_sum == target:
count += 1
return count
참고로 itertools의 product 부분의 출력 결과는 아래와 같다. 모든 경우의 1 혹은 -1의 리스트를 생성함.
from itertools import product
numbers = [1, 1, 1, 1, 1]
signs = list(product([1, -1] , repeat=len(numbers)))
signs
# 출력 결과
[(1, 1, 1, 1, 1),
(1, 1, 1, 1, -1),
(1, 1, 1, -1, 1),
(1, 1, 1, -1, -1),
....
*** 재귀함수 (Recursive function)
재귀함수란 자기 자신을 호출하는 함수이다.
함수가, 함수 내에서 자기 자신을 참조하여 호출한다.
이처럼 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.
아래 사례와 같은 끝이없는 거울 반사같은 반복적인 구조..
팩토리얼 함수는 대표적인 재귀함수로 아래와 같이 구현된다.
이 함수는 n이 0 또는 1인 경우 1을 반환하고, 그렇지 않은 경우 n을 n-1의 팩토리얼과 곱한 값을 반환하는데,
n 함수 안에서 호출된 factorial(n-1)은 n-1을 factorial(n-2)와 곱한 식일 것이고, 이 구조는 n 값만큼 끊이지 않고 이어질 것이다.
def factorial(n):
# 기본 사례: n이 0 또는 1인 경우
if n == 0 or n == 1:
return 1
# 재귀 사례: n * (n-1)! 호출
else:
return n * factorial(n - 1)
***깊이 우선 탐색 DFS / 너비 우선 탐색 BFS
두 알고리즘은 그래프나 트리와 같은 자료구조에서 사용된다.
- 깊이 우선 탐색(DFS, Depth-First Search) : 한 노드에서 시작하여 그래프의 최대 깊이까지 탐색한 후, 다시 돌아와 다른 노드를 탐색하는 방식으로, 스택이나 재귀 함수를 사용하여 구현
- 너비 우선 탐색(BFS, Breadth-First Search) : 한 노드에서 시작하여 인접한 모든 노드를 우선 방문한 후, 그 다음 레벨의 노드를 방문하는 방식으로, 큐를 사용하여 구현
간단한 DFS, BFS 구현 코드는 아래와 같다.
#### DFS
def dfs(graph, node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# 예시 그래프
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A', set()) # 출력 결과: A B D E F C
#### BFS
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=' ')
visited.add(node)
queue.extend(graph[node])
# 예시 그래프
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
bfs(graph, 'A') # 출력 결과: A B C D E F
trial2
이제 문제를 DFS와 재귀함수를 활용하여 풀어보자.
solution의 내부에 dfs라는 깊이우선 탐색을 수행하는 함수를 정의한다.
dfs 함수는 주어진 인덱스부터 숫자 리스트를 탐색하며 (len(numbers)까지) 현재까지의 합인 current_sum를 추적한다.
모든 숫자 리스트를 탐색하고 났을 때, current_sum이 목표값인 target과 같다면 1을 반환, 다르다면 0을 반환한다.
dfs라는 함수에서 재귀적인 호출 부분은 return 부분이다.
return 부분에서는, 현재의 숫자를 더하는 경우와 빼는 경우를 모두 고려한다.
index + 1를 통해 다음 숫자로 넘어가고, current_sum에 현재 숫자를 더하거나 빼면서 모든 경우의 수를 탐색한다.
최종 solution 함수의 출력값은 dfs(0,0)으로 설정함으로써, 값을 초기화 한다고 볼 수 있다.
numbers의 첫번째 숫자부터 시작하며, 현재의 합도 0으로 시작해서,
재귀적으로 계속 숫자를 더하거나 빼가면서 모든 경우의 수를 탐색하고, 주어진 목표 target을 만들 수 있는 경우를 반환한다.
def solution(numbers, target):
def dfs(index, current_sum):
# 모든 숫자를 다 탐색한 경우
if index == len(numbers):
# 현재 합이 목표값과 같으면 1 반환
if current_sum == target:
return 1
else:
return 0
# 현재 숫자를 더한 경우와 뺀 경우를 모두 탐색
return dfs(index + 1, current_sum + numbers[index]) + dfs(index + 1, current_sum - numbers[index])
# 초기 호출: 첫 번째 인덱스와 초기 합 0으로 시작
return dfs(0, 0)