재귀함수 복습으로 타겟 넘버 풀어보기

모든 경우의 수를 탐색하는 문제를 재귀함수 관점에서 복습하기 위해 프로그래머스 타겟 넘버 풀이를 정리한 글입니다.

개요

알고리즘 강의를 듣다 재귀함수와 관련된 프로그래머스 문제를 풀어보았습니다. 어디서부터 시작할지 몰라 고민하여 정답코드를 분석하는 방법으로 이해해 보려 했습니다. 이 문제는 주어진 숫자들의 순서는 바꾸지 않고, 각 숫자 앞에 + 또는 -를 붙여서 모든 경우의 수를 훑어본 후 target을 만들 수 있는 경우의 수를 구하는 문제입니다.

문제의 핵심은 모든 숫자를 꼭 한 번씩 다 돌아야 한다는 점이었습니다. 그리고 각 숫자마다 선택지는 두 가지였습니다.

• 현재 숫자를 더한다.
• 현재 숫자를 뺀다.

현재 숫자에 대해 더하거나 빼는 선택을 하고 나면 다음 숫자로 넘어갑니다. 그런데 다음 숫자에서도 해야 할 일은 똑같습니다. 또 더할지 뺄지를 선택하면 됩니다.

이처럼 현재 숫자를 처리한 뒤에도 남은 숫자들에 대해 같은 작업이 반복되기 때문에 재귀함수로 풀 수 있다고 이해했습니다. 재귀함수에는 지금 몇 번째 숫자를 보고 있는지 나타내는 index와, 지금까지 만든 합을 기억하는 total을 넘기면 됩니다.

먼저 정답 코드 보기

def solution(numbers, target):
    answer = 0

    def recursion(index, total):
        nonlocal answer

        if index == len(numbers):
            if total == target:
                answer += 1
            return

        recursion(index + 1, total + numbers[index])
        recursion(index + 1, total - numbers[index])

    recursion(0, 0)
    return answer

각 변수에는 이런 값이 담긴다고 이해했습니다.

• numbers: 문제에서 주어진 숫자 배열
• target: 만들어야 하는 목표 숫자
• answer: target을 만들 수 있는 경우의 수
• index: 지금 몇 번째 숫자를 보고 있는지
• total: 지금까지 더하고 뺀 결과
• recursion: 다음 숫자로 넘어가면서 가능한 경우를 계속 만들어보는 재귀함수

왜 재귀함수로 풀 수 있을까

예를 들어 numbers = [1, 1, 1, 1, 1], target = 3이라고 했을 때 각 숫자마다 선택지는 두 개입니다.

첫 번째 1을 볼 때도 선택지는 두 개입니다.

+1
-1

두 번째 1을 볼 때도 각각의 경우에서 다시 선택지가 두 개로 갈라집니다.

+1 +1
+1 -1
-1 +1
-1 -1

이런 식으로 숫자 하나를 볼 때마다 경우가 두 갈래로 나뉩니다. 그래서 전체 경우의 수는 2^n개가 됩니다.

재귀함수는 이 갈림길을 함수 호출로 계속 이어가는 방식입니다. 현재 숫자를 더하는 경우로 한 번 호출하고, 현재 숫자를 빼는 경우로도 한 번 호출합니다. 그러다가 모든 숫자를 다 사용한 시점에 total이 target과 같은지만 확인하면 됩니다.

작은 예시로 디버깅하듯 따라가기

같은 숫자가 반복되는 [1, 1, 1, 1, 1]보다 [1, 2, 3]으로 확인하면 index와 total의 변화를 구분하기 쉽습니다.

numbers = [1, 2, 3]
target = 0

재귀는 아직 아무 숫자도 사용하지 않은 상태에서 시작합니다.

recursion(0, 0)

+1 +2 -3 경로 하나만 디버깅하듯 따라가면 다음과 같습니다.

마지막 호출에서 index가 3, 즉 len(numbers)와 같아집니다. 모든 숫자를 사용했으므로 total이 target과 같은지 확인합니다.

if index == len(numbers):
    if total == target:
        answer += 1
    return

재귀함수는 이 경로만 확인하는 것이 아니라 각 숫자에서 +, -로 나뉘는 모든 경로를 확인합니다.

따라서 target = 0을 만드는 경우는 +1 +2 -3과 -1 -2 +3, 총 2가지입니다.

작은 입력으로 재귀 호출 하나를 따라간 뒤 전체 결과와 비교하면 index와 total이 어떤 역할을 하는지 확인하기 쉽습니다.

시간 복잡도

숫자마다 +와 - 두 가지 경로를 모두 확인합니다. 이 풀이는 중간에 탐색을 종료하지 않으므로 입력값과 관계없이 모든 조합을 방문합니다.

모든 계산 결과를 배열에 저장하면 별도로 O(2ⁿ) 공간이 필요합니다. 현재 코드는 결과를 저장하지 않고 answer만 증가시키므로 재귀 호출 스택에 필요한 O(n) 공간만 사용합니다.

핵심 포인트

• 이 문제는 각 숫자마다 +와 - 중 하나를 선택하는 문제입니다.
• 선택지가 두 갈래로 계속 나뉘기 때문에 재귀함수로 생각할 수 있습니다.
• index는 현재 보고 있는 숫자의 위치입니다.
• total은 지금까지 만든 합입니다.
• index == len(numbers)가 되면 모든 숫자를 사용한 상태라서 target과 비교합니다.
• 모든 합을 저장하지 않고, target이 되는 순간에 answer만 증가시키는 방식이 더 깔끔합니다.

개인적으로는 이렇게 정리했습니다.

타겟 넘버 문제는 재귀함수 코드를 외우기보다, index와 total이 어떻게 변하는지 작은 예시로 직접 따라가야 이해가 남는 문제라고 느꼈습니다.