[Algorithm] 프로그래머스 - 타겟 넘버

🏁 문제 소개

💡 문제 풀이

가장 먼저 문제를 보고 생각난건 트리구조였다. 결국 -1, +1 두개의 자식노드로 numbers의 크기의 깊이만큼 들어가는 트리구조로 생각했다. [4, 1, 2, 1] 같은 경우는 아래 상태로 나타낼 수 있을 것 같다.

DFS

재귀함수를 활용하여 깊이우선탐색을 구현했다.

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

func dfs(_ numbers: [Int], _ target: Int, _ sum: Int, _ depth: Int) -> Int {
    if depth == numbers.count {
        return sum == target ? 1 : 0
    }
    
    return [-1, +1].reduce(0) { $0 + dfs(numbers, target, sum + numbers[depth] * $1, depth + 1) }
}

BFS

큐의 개념을 사용했지만 removeFirst 함수를 쓰지 않고, index로 관리했다.

func solution(_ numbers: [Int], _ target: Int) -> Int {
    bfs(numbers, target)
}

func bfs(_ numbers: [Int], _ target: Int) -> Int {
    var queue: [(sum: Int, depth: Int)] = [(0, 0)]
    var result = 0
    var index = 0

    while index < queue.count {
        let current = queue[index]
        let sum = current.sum
        let depth = current.depth
        
        if depth == numbers.count {
            result += sum == target ? 1 : 0
        } else {
            queue.append((sum + numbers[depth], depth + 1))
            queue.append((sum - numbers[depth], depth + 1))
        }
        
        index += 1
    }
    
    return result
}

🤔 문제 풀이 결과

특이한게 BFS의 경우 DFS보다 약 3배 이상 빠른것을 볼 수 있었다. 

왼쪽 dfs, 오른쪽 bfs

큐에서 해제하지 않기 때문에 물론 용량은 BFS가 더 많이 잡아먹기 때문에 많이 쓰지만, 속도는 확실히 유의미하게 빠른 것을 알 수 있다.

🔥 재귀함수 vs 반복문

재귀함수, 반복문의 차이인 것을 알게 되었다. 재귀함수의 경우 호출 스택(Call Stack)을 사용하여 함수 호출을 계속 저장하고, 반환하는 과정을 거치기 때문에 단순히 반복문을 사용하는 경우보다 메모리 사용량도 증가하고, 스택 오버플로우의 위험성이 더 크다고 한다. 물론 나의 경우 queue에서 dequeue를 해주지 않고, 계속 쌓아나갔기 때문에 메모리 사용량이 더 많았던 것 같다.

 

선형적 작업의 경우 재귀함수보다는 반복문을 쓰는 것이 더 효율적일 것 같다.