성능 요약
- 메모리: 78 MB, 시간: 0.31 ms - Answer Code1(2023.02.13)
구분
코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS）
Answer Code(2023.02.13)
class Solution {
int [] numbers;
int target;
int answer;
void dfs(int index, int sum) {
//1. 탈출 조건
if(index == numbers.length) {
if(sum == target) answer++;
return;
}
//2. 수행 동작
dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);
}
public int solution(int[] numbers, int target) {
answer = 0;
this.numbers = numbers;
this.target = target;
dfs(0, 0);
return answer;
}
}
Answer Code1 - 문제 풀이
-
수행 동작 : 인덱스 값은 현재 인덱스에 하나를 더하거나 뺀 값으로 넘겨주면 된다. => index + 1 또는 index - 1
-
왜냐하면 경우의 수가 2가지(+ 또는 -)이기 때문이다.
-
sum 에는 numbers[index]를 더하거나 빼주면 된다. (즉 여테까지 만들어진 누적합에 현재 index 번째 숫자를 더해서 다음 dfs 함수를 call 해주는 의미)
-
-
탈출 조건 : 재귀함수는 영원하게 불러주기 때문에, 탈출 조건은 현재 재귀함수가 call된 인덱스(depth 길이)가 numbers.length만큼 되면 빠져나오기로 한다.
- 마지막 노드까지 탐색했을 때(index와 numbers 배열의 길이가 같은 경우), target과 sum의 값이 일치하면 answer 값을 증가시키고 탈출한다.
Answer Code2(2023.11.07)
class Solution {
int answer = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, 0, target, 0);
return answer;
}
// 깊이 우선 탐색
public void dfs(int[] numbers, int depth, int target, int sum){
if(depth == numbers.length){ // 마지막 노드 까지 탐색한 경우
if(target == sum) answer++;
} else {
dfs(numbers, depth + 1, target, sum + numbers[depth]); // 해당 노드의 값을 더하고 다음 깊이 탐색
dfs(numbers, depth + 1, target, sum - numbers[depth]); // 해당 노드의 값을 빼고 다음 깊이 탐색
}
}
}
Answer Code2 - 문제 풀이
-
깊이 우선 탐색 알고리즘을 이용
-
마지막 노드까지 탐색했을 때 타켓 넘버와 결과값이 같으면 정답 카운트 증가
정답 카운트를 저장할 전역변수 answer 선언 및 초기화
class Solution {
int answer = 0;
}
깊이 우선 탐색 알고리즘
public void dfs(int[] numbers, int depth, int target, int sum) {
// numbers : 알고리즘을 실행할 대상 배열
// depth : 노드의 깊이
// target : 타겟 넘버
// sum : 이전 노드 까지의 결과 값
}
-
마지막 노드까지 탐색했을 경우, 즉 depth와 numbers 배열의 길이가 같을 때에는 target과 sum값을 비교하여 일치하면 answer 카운트 증가
-
탐색할 노드가 남아있는 경우 이전 노드까지의 합에서 현재 노드 값을 더하고 빼는 두 가지 경우로 깊이 우선 탐색 알고리즘 재실행
public void dfs(int[] numbers, int depth, int target, int sum) {
if(depth == numbers.length) { // 마지막 노드까지 탐색한 경우
if(target == sum) answer++;
} else { // 탐색할 노드가 남아있는 경우
dfs(numbers, depth + 1, target, sum + numbers[depth]); // 해당 노드의 값을 더하고 다음 깊이 탐색
dfs(numbers, depth + 1, target, sum - numbers[depth]); // 해당 노드의 값을 빼고 다음 깊이 탐색
}
}
초기 depth, sum 값을 0 으로 세팅하여 알고리즘 실행후 answer 값 리턴
public int solution(int[] numbers, int target) {
dfs(numbers, 0, target, 0);
return answer;
}
Review
Answer Code1
-
재귀함수 관련 문제를 구현할 때 [1] 수행 동작을 먼저 구현한 뒤 [2] 탈출 조건을 구현한다는 것을 기억하자.
-
재귀함수를 머릿속으로 이해가 되지 않는다면 자세히 그려보자.
Answer Code2
- Answer Code1과 같은 DFS이지만, 다르게 풀어봤다. 확실히 이전보다 더 읽기가 편해졌다.