가장 먼저, 문제를 파악해보자.
부분 수열이란 무엇을 말하는 것일까?
나는 처음에 수열 내에서 다시 고른 연속된 수열이라고 생각했다.
하지만 부분 수열의 정의는 아래와 같다.
원래 수열의 순서를 그대로 유지한 채 뽑아낸 새로운 수열
즉, 굳이 연속되지 않아도 원래 수열에서의 순서만 유지되면,
그것은 부분 수열이라고 인정하겠다는 것이다.
순서를 유지하며 연속성을 유지해야 하는 것은 부분 순서 라고 칭한다.
이제 부분 수열의 정의를 알았으니, 문제의 조건을 확인해보자.
최대 10만의 정수가 최대 20개 주어지고 최대 100만의 목표 합이 주어진다.
정수 범위를 크게 벗어나지 않는 문제로 판단된다.
그럼 조건에 맞추어 어떤 방식으로 문제를 풀어나갈까?
우리가 해야할 일은 수열 속에서 순서를 바꾸지 않고 수를 고르는 것이다.
1개만 고를 때, 2개 고를 때, 3개, … N개 고를 때 모두가 후보가 된다.
즉, 이 문제는 Brute force(완전 탐색) 방식으로 풀어야 하는 문제이다.
그럼 단순히 for문을 돌려서 부분 수열을 뽑아낼 수 있을까?
2개를 고르는 경우를 한 번 생각해보자.
외부 for문을 통해 하나를 고르고, 내부 for문에서 하나를 더 고른다.
이것을 다른 자료구조에 저장하고 둘을 더하여 목표 합과 비교한다.
자료구조에서 해당 수를 빼내고, 내부 for문을 통해 다음 수로 진행한다.
위의 과정은 틀림없이 맞는 과정이다. 그리고 과정을 보았을 때,
2개를 고르는 경우엔 2중 for문으로 해결을 할 수 있다.
그런데 만약 3개, 4개를 골라야 하는 경우엔 3중 4중 for문이 될 것이다.
이 때, 우리는 아래와 같이 생각해볼 수 있다.
계속 같은 동작을 반복해서 수행하는데, 재귀적으로 구현하면 되지 않을까?
그렇다. for문을 순회하는 함수를 작성하고, 재귀적으로 함수를 실행시키면?
매개변수로 고른 수와 합을 넘기며, N중 for문을 작성하지 않아도 구현이 가능하다.
아래와 같이 코드를 짜보았다.
int num = 0, target = 0, answer = 0;
int seq[20];
void backtrack(int idx, int sum, int limit, int depth) {
// idx로 다음 수를 고르고, sum으로 합을 넘긴다.
// limit로 고를 개수를 정하고, depth로 고른 개수를 넘긴다.
if (depth == limit) {
if (sum == target)
answer++;
return;
}
for (int i = idx + 1; i < num; i++)
backtrack(i, sum + seq[i], limit, depth + 1);
// 재귀적으로 해당 for문을 반복하면, 모든 수의 조합을 찾을 수 있다.
}
int main(){
cin >> num >> target;
for (int i = 0; i < num; i++)
cin >> seq[i];
// 선택할 수 있는 수는 1개 ~ N개까지 가능하다.
for (int i = 1; i <= num; i++)
backtrack(-1, 0, i, 0);
cout << answer << '\n';
return 0;
}재귀적으로 for문 안에 for문 안에 for문.. 을 찾아다닌다.
DFS와 유사하게 모든 node를 탐색하되, 조건을 걸어 시간을 줄인다.
고르기로 정한 개수의 수를 모두 골랐으면 더 이상 진행하지 않는다.
이런 방식을 우리는 Backtracking 이라고 부른다.
재귀를 통한 완전 탐색의 문제에 주로 사용되는 방식이다.
과거 기록에, 아무 생각없이 방문 배열을 사용하여 푼 기록이 있었다.
사실 사용해도 무방하지만, 사용하지 않고도 생각하면 풀 수 있다.
그 때의 나는 왜 사용했는지도 모르고 사용했을 것이다. 반성하자.