[day17] 코딩테스트 알고리즘 - 깊이/너비 우선 탐색 (타겟넘버) (feat.파이썬 product)

프로그래머스

 

문제 풀이 설명

문제는 DFS Depth-First-Search 깊이 우선 탐색이다.

 

문제를 보면 이진트리로 탐색을 한다는 것의 힌트를 얻을 수 있다.

1. 더하거나 빼기 (2가지 경우로 뻗어 나간다)

 

우선 기준점을 [0]으로 시작한다. 일단 0을 루트노드로 가지는 것이다.

각 노드는 이진트리로 2개의 자식 노드를 가질 수 있다. 이 자식 노드는 각각에 -1 과 +1을 더한 값들이다 .

이렇게 numbers를 전부 탐색하면서 1,-1를 더한 자식 노드를 만들어간다.

결과적으로, numbers의 수들을 빼거나 더하며 만들어진 값이 리프노드에 나오게된다 (*리프노드: 자식 노드가 없는 마지막 노드)

여기서 target에 해당하는 값을 찾으면 된다.

 

참고 코드

def solution(numbers, target):
  count = 0
  tree = [0]
  for i in numbers:
    sub = []
    for j in tree:
      sub.append(j + i)
      sub.append(j - i)
    tree = sub
    print(tree)
  return tree.count(target)

 

다른이의 코드

python의 문법 product으로 아주 간결하게 풀어낸 코드가 있어서 가져왔다.

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l))) #중복순열
    return s.count(target)

 

---

python product문법 정리

python의 product는 중복 순열이다.

중복 순열은 선택한 것을 기준으로 두고 배열을 돌며 중복적으로 조합한다. 

python의 permutation은 일반 순열로 "배열의 조합을 모두 구하는 것"이다.

python의 combination은 permutations의 중복을 제거한다.

당연하겠지만, 이 셋은 서로 다르다. 

말은 어렵지만 아래 코드를 보면 쉽게 이해할 수 있다.

 

 

product, permutations, combination 비교샷

print(list(product(arr1,repeat=2)))
#[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

print(list(permutations(arr1, 2)))
#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

print(list(combinations(arr1, 2)))
#[(1, 2), (1, 3), (2, 3)]

 

product 사용법

from itertools import product

arr1 = [1,2,3]
print(list(product(arr1)))
#[(1,), (2,), (3,)]

print(list(product(arr1,repeat=2)))
#[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

arr2 = [[1,2,3], [1,2], [4,5]]
print(list(product(arr2)))
#[([1, 2, 3],), ([4, 5],)]
print(list(product(*arr2)))
#[(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)]
print(list(map(sum, product(*arr2))))
#[5, 6, 6, 7, 7, 8]