[PROGRAMMERS] 깊이/너비 우선 탐색 : 타겟넘버 Python

사실 이 문제는 어렵지는 않지만, 제한사항과 문제 카테고리가 없었으면 좀 헤매었을 것 같다. 왜냐하면 완전 탐색 문제만 보면 DP문제가 아닌가? 하는 겁이 나기 때문이다.

하지만, 위에 말한것 처럼 제한사항에서 주어지는 숫자 개수가 20개 이하인걸 확인한다면, 쉽게 풀 수 있을 것이다.

이문제는 숫자들의 배열과 타겟넘버가 주어질 때, 숫자들의 배열의 합과 차로 타깃 넘버를 만들 수 있는 방법의 개수를 묻는 문제이다. 

더하거나 뺄 수 있다는 부분에서 부분집합(itertools)를 활용하기에는 조금 어려움이 있을 것 같아 나는 완전 검색(DFS) 방식으로 문제를 풀었다.

문제코드

원하는 타겟넘버가 되는 조건을 종료 조건으로 그전까지는 배열을 진행하면서 합과 차를 각각 구해보는 전형적인 완전 탐색 풀이법을 사용해 보았다.

사실 풀면서 시간초과를 대비하여, 절대 타깃 넘버가 될 수 없는 경우를 계산하여 가지치기할 방법을 생각하고 있었는데, 다행히 가지 치기 없이 시간 초과를 피할 수 있었다.

요즘 프로젝트가 많아 알고리즘에 투자할 시간이 이전보다 줄어들었지만, 이기회를 활용하여 기초 문제를 눈감고 풀 수 있을 정도가 되도록 복습을 해보아야겠다.

하루 한개 알고리즘 파이팅!!