역추적(Backtracking)이란?
역추적은 복잡한 최적화 및 탐색 문제를 해결하는 대표적인 알고리즘 기법입니다. 문제를 단계별로 진행하면서, 현재 경로가 해답으로 이어질 수 없다고 판단되면 즉시 해당 경로를 포기하고 이전 상태로 되돌아가(백트래킹) 다른 가능성을 탐색합니다. 이러한 '가지치기' 과정 덕분에 불필요한 탐색을 줄여 전체 완전 탐색보다 효율적으로 동작할 수 있습니다.
부분집합 합(SubSet Sum) 문제
부분집합 합 문제는 주어진 집합에서 원소들을 선택하여, 선택된 원소들의 합이 목표 숫자 K와 정확히 일치하는 부분집합을 찾는 문제입니다. 이때 집합의 모든 원소는 양수이며 중복이 없다는 조건이 주어집니다.
해결 방식은 간단합니다. 가능한 부분집합을 하나씩 생성해 보면서, 각 부분집합의 합이 목표값과 같은지 확인하면 됩니다. 아래 예제 프로그램을 통해 직접 구현 방법을 살펴보겠습니다.
예제 코드
#include <stdio.h>
#include <stdlib.h>
static int total_nodes;
void printValues(int A[], int size){
for (int i = 0; i < size; i++) {
printf("%*d", 5, A[i]);
}
printf("\n");
}
void subset_sum(int s[], int t[], int s_size, int t_size,
int sum, int ite, int const target_sum){
total_nodes++;
if (target_sum == sum) {
printValues(t, t_size);
subset_sum(s, t, s_size, t_size - 1, sum - s[ite], ite + 1, target_sum);
return;
}
else {
for (int i = ite; i < s_size; i++) {
t[t_size] = s[i];
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1, target_sum);
}
}
}
void generateSubsets(int s[], int size, int target_sum){
int* tuplet_vector = (int*)malloc(size * sizeof(int));
subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);
free(tuplet_vector);
}
int main(){
int set[] = { 5, 6, 12 , 54, 2 , 20 , 15 };
int size = sizeof(set) / sizeof(set[0]);
printf("The set is ");
printValues(set , size);
generateSubsets(set, size, 25);
printf("Total Nodes generated %d\n", total_nodes);
return 0;
}실행 결과
The set is 5 6 12 54 2 20 15 5 6 12 2 5 20 Total Nodes generated 127
코드 동작 원리
위 코드의 핵심 함수인 subset_sum()은 다음과 같은 방식으로 동작합니다.
- 배열 s: 입력으로 주어진 원본 집합을 저장합니다.
- 배열 t: 현재 탐색 중인 임시 부분집합(튜플 벡터)을 저장합니다.
- sum: 현재까지 선택된 원소들의 누적 합을 나타냅니다.
- ite: 다음에 탐색할 시작 인덱스로, 같은 원소를 중복 선택하지 않도록 제어합니다.
재귀 호출이 진행되면서 sum이 target_sum과 일치하면 해당 부분집합을 출력하고, 추가적인 조합을 찾기 위해 마지막 원소를 제외한 상태로 다시 탐색을 이어갑니다. 합이 목표값에 도달하지 않으면 다음 원소를 하나씩 추가하며 재귀적으로 탐색을 계속합니다.
실행 결과를 보면 집합 {5, 6, 12, 54, 2, 20, 15}에서 합이 25가 되는 두 개의 부분집합 {5, 6, 12, 2}와 {5, 20}이 성공적으로 출력된 것을 확인할 수 있습니다. 또한 총 127개의 노드를 탐색했는데, 이는 역추적 기법이 탐색 공간을 어떻게 순회하는지 보여주는 지표입니다.