2/17기록 - Programmers 타겟넘버(dfs문제)

<문제>

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

(코딩테스트 연습 - 타겟 넘버 | 프로그래머스 (programmers.co.kr) 참고)

코딩테스트 연습 - 타겟 넘버

 

문제는 이러하다. numbers[] 배열 안의 수를 적절히 조합하여 target하는 수가 만들어지면 count 해 주어서 return 시키면 된다. 간단한 문제처럼 보일 수 있겠지만 솔직히 dfs, bfs 문제라고 나와있지 않는 이상 지금 실력으로는 영원히 못풀것 같았다. 

 

문제를 처음 볼 때 numbers[] 배열 끝까지 탐색하여 조합해야 하므로 깊이우선탐색(dfs)를 쓰면 되겠다는 생각을 했다.

 

 

**깊이 우선 탐색(DFS, Depth-First Search)

깊이 우선 탐색이란

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
1. 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
3. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

 

깊이 우선 탐색(DFS)의 특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.

2. 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
3. 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

 

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html 

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

이 블로그에 깊이 우선 탐색에 대해서 굉장히 자세하게 설명하고 있어 내용을 조금 첨부해 보았다. 

 

 

깊이 우선 탐색(dfs)의 내용은 알겠는데 저 코드를 보고 뭘 어쩌라는 건지 솔직히 이해가 잘 안갔다. 솔직히 이 문제는 dfs까지 생각한 후 한참 고민하다가 구글을 조금 참고 했다. 구글을 참고해 보니 dfs로 함수를 하나 만들고 함수를 재귀형태로 구현하여 호출하는 방식을 사용하고 있었다. 이제 조금 감이 잡혀서 문제를 풀어 보았다.

 

 

코드를 보며 이해해 보자. dfs 탐색을 할 함수를 하나 선언하는데, 어디까지 갈지 idx, 결과를 나타낼 result 변수까지 선언해 주고, idx가 numbers 배열 길이 일 때 result가 target과 같으면 정답이 나온 경우이므로 answer 개수를 ++ 시켜준다. idx가 numbers 배열 길이가 아니라면 dfs를 재귀적으로 나타내어 idx를 하나씩 올리면서 result 값을 더하거나 빼준다. 

 

이렇게 만들어진 dfs 함수를 호출해서 answer를 return 하는데, 여기서 나는 idx가 0일 경우 어짜피 정해진 상태니까 idx를 1부터 시도해 보려고 했다. idx를 1로 초깃값을 정해주고, numbers[0]을 음수, 양수로 나누어 result로 넣어주었다. 

 

다 끝나고 보니 호출할 때 dfs(numbers, target, 0, 0)으로 그냥 해주면 더 간단하게 풀 수 있었다. 괜히 1부터 하는게 조금더 빠르지 않을까 하다가 result가 더 복잡해진 듯 했다. ㅠㅠㅠ

 

2/17 기록 끝!!!!!!!!