문제

링크

numbers 배열의 각 숫자 앞에 + 또는 - 를 붙여 target 값을 만드는 모든 경우의 수를 구해보자.

---

풀이

여러 방법으로 풀 수 있다.

1. 재귀 풀이

f(idx,result)=f(idx+1, result+numbers[idx])+f(idx+1, result−numbers[idx])

우리가 구하고자 하는 값을 f(idx,result) 로 표현하자.
현재 인덱스인 idx와 누적합인 result를 합해 target을 구하자는 것이다.

이때, 이 값은 누적합과 "idx번째 숫자를 더한 경우의 수", "idx번째 숫자를 뺀 경우의 수"를 각각 구해서 더해서 구한다.

n의 길이만큼 prefixSum 함수를 사용하며 이를 구해보자.

def solution(numbers, target):
    n = len(numbers)

    def prefixSum(idx, result):
        
        # 기저조건
        if idx == n: 
            if result == target: 
                return 1 
            else: 
                return 0
            
        return (
            prefixSum(idx + 1, result + numbers[idx]) 
            +  prefixSum(idx + 1, result - numbers[idx]) # + - 인 경우 모두 구하고, 함수 실행 결과값 더하기.
        )

    return prefixSum(0, 0) # 재귀로 n (numbers) 모두 순회

---

2. 데카르트곱 풀이

데카르트 곱(Cartesian Product)이란 여러 집합에서 원소를 하나씩 뽑아 만들 수 있는 모든 조합을 뜻한다.

이를 이용해 타겟 넘버를 풀이하려면 itertools.product()를 사용해 각 자리마다 +, - 두 가지 선택지를 갖는 모든 부호 조합을 생성하고, 그 중 target을 만족하는 경우의 수를 세면 된다.

from itertools import product

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    
    # 각 자리마다 (+, -) 두 가지 선택지가 있는 조합을 전부 생성
    for signs in product([1, -1], repeat=n):
        total = sum(s * num for s, num in zip(signs, numbers))
        if total == target:
            answer += 1
    
    return answer

---

3. dp 풀이

target과의 차이(remaining)를 key로, 그 remaining을 만드는 경우의 수를 value로 갖는 딕셔너리를 만들어보자.

target에서 시작해 numbers를 하나씩 처리하며, 각 숫자를 더한 경우와 뺀 경우로 remaining을 갱신하고 이 경우의 수를 딕셔너리에 누적한다.

from collections import defaultdict

def solution(numbers, target):
    ways = defaultdict(int)
    ways[target] = 1  # 초기 상태(부분 문제): 숫자 0개 사용, remaining=target인 경우 1가지

    for n in numbers:
        next_ways = defaultdict(int)
        for remaining, cnt in ways.items():
            # 이전 단계(작은 부분 문제)의 결과(cnt)를 그대로 이용해
            # 현재 숫자를 더하거나 뺀 다음 단계(큰 부분 문제)의 결과를 누적
            next_ways[remaining - n] += cnt
            next_ways[remaining + n] += cnt
        ways = next_ways  # dp 테이블 갱신: 한 단계 더 큰 부분 문제로 확장

    return ways[0] 
    ```

---

생각한 것

복습을 통한 사고확장

처음 문제를 풀이할 때는 재귀 풀이 방법밖에 떠올리지 못했는데,
문제를 다시 보니 데카르트 곱, DP 등 다양한 방법으로도 해결할 수 있을 듯 하다는 생각이 들었다.

꾸준히 알고리즘을 복습하면서 사고가 이전보다 확장되었음을 느낀다.

알고리즘 선택 기준

오늘 포스팅에서 다뤄보았듯, 알고리즘의 풀이에는 정말 다양한 방법이 있다.

그리고 문득, 알고리즘을 선택할 때 시간 복잡도와 공간 복잡도를 고려하는 것도 중요하지만, 실행 환경과 요구사항에 맞는 알고리즘을 선택할 수 있는 능력 역시 중요하다는 생각이 들었다.

실행 환경이나 메모리 제약, 코드의 유지보수성 등 프로젝트마다 고려해야 할 요소는 모두 다르다.
같은 문제를 해결하는 알고리즘이라도 대량의 데이터를 반복적으로 처리해야 하는 서비스에서는 중복 계산을 줄이는 DP가 더 적합할 수 있고,
빠르게 기능을 구현해야하거나 알고리즘의 흐름을 직관적으로 표현하는 것이 중요한 상황에서는 재귀가 더 적절한 선택이 될 수도 있듯 말이다.

여러 관점에서 문제를 바라보고, 각 알고리즘의 장단점을 이해하여 상황에 맞는 해결 방법을 선택할 수 있는 사람이 되고싶다.

그러기 위해서는 cs와 알고리즘을 함께 익혀가야 할 듯한데,
시스터디(혹은 씨스터디) 친구들이 있어 꾸준히 이런 일을 할 수 있는 것 같아 참 좋다.
ㄹㅇㄹㅇㄹㅇ이다.

굿.