[DFS] 프로그래머스 Lv2. 타겟 넘버 - Python

🗂️ 문제

링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

👀 배운 코드

1. DFS 기반 코드

재귀 방식으로 모든 경우의 수에 대한 계산을 수행한다.

def solution(numbers, target):
    global answer
    answer = 0
    
    def DFS(i, sum):
        global answer
        if i == len(numbers):
            if sum == target:
                answer += 1
            return
        
        DFS(i+1, sum+numbers[i])
        DFS(i+1, sum-numbers[i])
    
    DFS(0, 0)
    
    return answer

 

2. Product 기반 코드

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    cases = list(map(sum, (product(*l))))
    
    return cases.count(target)

1. product(*l): itertools.product를 사용하여 가능한 모든 조합을 생성한다.
2. map(sum, product(*l)): 생성된 각 조합에 대해 sum 함수를 적용하여 각 조합의 합을 계산한다.
3. list(map(sum, (product(*l)))): map 객체를 리스트로 변환하여 모든 합을 리스트로 반환한다.
4. target에 해당하는 값의 개수를 센다.

 

🧐 배운 점

1. itertools

itertools는 파이썬 표준 라이브러리로, 반복(iterable) 처리를 더 효율적으로 수행할 수 있는 도구들을 제공한다.

• permutations
  • 순열, 순서를 고려하고 중복을 허용하지 않는다.

from itertools import permutations

data = ['A', 'B', 'C']

# 길이 2의 순열
result = list(permutations(data, 2))
print(result)

# 출력: [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

•  combinations
  • 조합, 순서를 고려하지 않고 중복을 허용하지 않는다.

from itertools import combinations

data = ['A', 'B', 'C']

# 길이 2의 조합
result = list(combinations(data, 2))
print(result)

# 출력: [('A', 'B'), ('A', 'C'), ('B', 'C')]

• product
  • 데카르트 곱(Cartesian Product), 순서를 고려하고 중복을 허용한다.

from itertools import product

# 1. 두 리스트의 데카르트 곱
data1 = [1, 2]
data2 = ['A', 'B']
result = list(product(data1, data2))
print(result)
# 출력: [(1, 'A'), (1, 'B'), (2, 'A'), (2, 'B')]

# 2. 하나의 리스트를 두 번 반복한 조합
data = ['A', 'B']
result = list(product(data, repeat=2))
print(result)
# 출력: [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

• combinations_with_replacement
  • 순서는 고려하지 않고 중복은 허용한다.

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

# 길이 2의 조합 (중복 허용)
result = list(combinations_with_replacement(data, 2))
print(result)

# 출력: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

 

2. list(map(sum, product(*l)))에서 지연 평가와 즉시 평가

파이썬에서 product와 map 함수는 지연 평가(lazy evaluation)를 수행한다.

즉, 결과를 미리 계산하지 않고 필요할 때(예: 루프에서 값이 요청될 때) 계산을 수행한다.

• map 객체 자체는 계산을 미루고 있다가, list()로 변환하거나 루프에서 값을 요청할 때 계산을 실행한다.
• list(map(...))를 호출하면, map의 결과를 모두 한꺼번에 계산하고 리스트에 저장한다. 메모리를 더 사용하지만, 결과를 즉시 얻을 수 있다.