Skip to content

[Algorithm] 타겟 넘버 #11

Description

@hwangJi-dev

📌 TODO

  • 문제 풀이
  • 정리

🎢 타겟 넘버

💬 Idea

  • DFS를 이용하여 깊이우선탐색을 진행하며 +, - 연산을 수행하자

    → 재귀함수를 호출하자!

  • 연산이 +, - 2가지 경우가 있으므로

      • 연산을 수행하는 dfs함수와 - 연산을 수행하는 dfs 함수를 모두 호출한다.
    • 모든 경우의 수에 +, - 연산을 수행하여 타겟 넘버에 도달하는 경우를 뽑아낼 수 있도록 재귀함수를 호출한다.

💬 풀이


import Foundation

var answer: Int = 0

func solution(_ numbers:[Int], _ target:Int) -> Int {
dfs(numbers: numbers, target: target, index: 0, sum: 0)
return answer
}

func dfs(numbers: [Int], target: Int, index: Int, sum: Int) {
if index == numbers.count {
if target == sum {
answer += 1
}
return
}

dfs(numbers: numbers, target: target, index: index + 1, sum: sum + numbers[index])
dfs(numbers: numbers, target: target, index: index + 1, sum: sum - numbers[index])

}

소요시간 : 1시간 30분


💬 알게된 것

✅ DFS/BFS

  • DFS에서는 재귀함수 호출을, DFS에서는 큐 사용을 주로 하여 문제를 풀이한다는 것을 알게 되었다.

    DFSBFS
    동작 원리스택
    구현 방법재귀 함수 이용큐 자료구조 이용

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions