(DFS/BFS) 타겟 넘버

yejichoi·2023년 5월 5일
0

알고리즘 스터디

목록 보기
49/153
post-thumbnail

타겟 넘버

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

-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

제한 사항

  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numberstargetreturn
[1, 1, 1, 1, 1]35
[4, 1, 2, 1]42

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

BFS / DFS

🥨 BFS 정답 풀이

  • numbers의 숫자를 더하거나 뺀 경우를 수평적으로 추가
  • leaves리스트에 모든 계산 결과가 담기게 됨. 이후 target값과 비교해서 결과 출력
def solution(numbers, target):
#   leaves = [0]          # 모든 계산 결과를 담자      
#   count = 0 

#   for num in numbers : 
#     temp = []
	
#     # 자손 노드 
#     for leaf in leaves : 
#       temp.append(leaf + num)    # 더하는 경우 
#       temp.append(leaf - num)    # 빼는 경우 

#     leaves = temp 

#   # 모든 경우의 수 계산 후 target과 같은지 확인 
#   for leaf in leaves : 
#     if leaf == target : 
#       count += 1

#   return count

    sup= [0]
    for i in numbers:
        sub = []
        for j in sup : 
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

🥨 DFS 정답 풀이

  • BFS가 수평적으로 더해 한꺼번에 모든 결과값을 얻었다면, DFS를 이용할 땐 하나씩 비교
  • depth 변수 값을 통해 탐색 중인 트리의 깊이를 알 수 있움
  • 트리 끝에 도착했다면, number값을 모두 더한 값을 비교
def solution(numbers, target):
    answer = DFS(numbers, target, 0)
    return answer

def DFS(numbers, target, depth):
    answer = 0
    if depth == len(numbers): # 끝까지 닿았을 때 
       # print(numbers)
        if sum(numbers) == target:# 끝까지 닿은 것 중에서 타겟이랑 같으면 
            return 1
        else: return 0
    else: #depth가 0,1,2,3 일 때 
        #answer = 0
        answer += DFS(numbers, target, depth+1)
        numbers[depth] *= -1
        answer += DFS(numbers, target, depth+1)
        print(answer)
        return answer
        
def solution(numbers, target):
  answer = 0
  queue = [[numbers[0],0], [-1*numbers[0],0]]
  #[[4,0], [-4,0]]
  
  n = len(numbers) # n =4 
  print(queue,n)
  while queue:
      temp, idx = queue.pop()
      idx += 1
     # print(temp,idx)
      if idx < n:
          print([temp+numbers[idx], idx],[temp-numbers[idx], idx])
          queue.append([temp+numbers[idx], idx])
          queue.append([temp-numbers[idx], idx])
          print(queue)
      else:
          if temp == target:
              answer += 1
  return answer
def solution(numbers, target):
  
  def dfs(level,current_sum ,answer): 
      if level >= len(numbers):
          if current_sum == target:
              answer += 1
          return answer

      
      answer = dfs(level+1, current_sum + numbers[level], answer)
      answer = dfs(level+1, current_sum - numbers[level], answer)
      return answer
  
  return dfs(0,0,0)

dfs의 else 부분이 이해가 안간다....왜지...도대체 왜지,...

#이진수 풀이법
def solution(n, t):
    answer = 0
    for i in range(2**len(n)):
        tmp = []
        for j in range(len(n)):
            if i & (2**j) == 0:
                tmp.append(n[j])
            else:
                tmp.append(-1*n[j])
        if sum(tmp) == t:
            answer += 1        
    return answer

0개의 댓글