메모이제이션(Memoization) 적용을 통한 성능 개선 (2) - 백트래킹

백트래킹 성능개선

 

반응형

 백트래킹(Backtracking)은 문제를 해결하기 위해 모든 가능한 경우를 탐색하되 가지치기를 통해 확인할 필요가 없는 경우는 생략하는 기법입니다. 하지만, 중복된 계산이 많아질 경우 성능 문제가 발생할 수 있습니다. 이런 문제를 해결하기 위해 메모이제이션(Memoization)을 적용하면 효율을 크게 향상시킬 수 있습니다. 이번 글에서는 백트래킹과 메모이제이션을 결합하는 방법을 설명하고, C언어, Java, Python으로 구현한 예제 코드를 통해 두 접근법의 차이를 비교해 보겠습니다.

---

 

1. 백트래킹과 메모이제이션이란?

백트래킹

• 가능한 모든 경우를 재귀적으로 탐색하며 해를 찾는 알고리즘입니다.
• 조건에 맞지 않는 경로는 빠르게 포기(가지치기, Pruning)하여 탐색을 줄이는 방식으로 동작합니다.

메모이제이션

• 계산된 값을 저장해 동일한 계산을 반복하지 않도록 하는 기법입니다.
• 백트래킹과 결합하면 중복 계산을 방지하여 성능을 극대화할 수 있습니다.

 

참고) 백트래킹과 메모이제이션에 대한 자세한 내용은 아래 글들을 참고하면 좋습니다.

2024.12.20 - [알고리즘] - 백트래킹(Backtracking) 알고리즘 - 가지치기의 중요성(개념,원리,시간복잡도, C언어,Java,Python 예시코드)

백트래킹(Backtracking) 알고리즘 - 가지치기의 중요성(개념,원리,시간복잡도, C언어,Java,Python 예시코

2024.12.20 - [알고리즘] - 다이나믹 프로그래밍 개념부터 활용까지 완벽 정리 - 메모이제이션, 반복문, C, Java, Python 예시코드

다이나믹 프로그래밍 개념부터 활용까지 완벽 정리 - 메모이제이션, 반복문, C, Java, Python 예시코

---

 

2. 예제 문제: 집합의 부분합 문제

주어진 배열과 목표 값이 있을 때, 배열의 일부 원소를 더해 목표 값을 만들 수 있는지 판단하는 문제를 예제로 들어 보겠습니다.

C 언어 구현

백트래킹 코드

#include <stdio.h>
#include <stdbool.h>

bool subsetSum(int arr[], int n, int target) {
    if (target == 0) return true;
    if (n == 0 || target < 0) return false;

    // 현재 원소 포함 여부를 재귀적으로 탐색
    return subsetSum(arr, n - 1, target - arr[n - 1]) || subsetSum(arr, n - 1, target);
}

int main() {
    int arr[] = {2, 4, 6, 10};
    int target = 16;
    printf("Subset sum result: %s\n", subsetSum(arr, 4, target) ? "True" : "False");
    return 0;
}

메모이제이션 코드

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int memo[100][100];

bool subsetSum(int arr[], int n, int target) {
    if (target == 0) return true;
    if (n == 0 || target < 0) return false;

    if (memo[n][target] != -1) return memo[n][target];

    return memo[n][target] = subsetSum(arr, n - 1, target - arr[n - 1]) || subsetSum(arr, n - 1, target);
}

int main() {
    int arr[] = {2, 4, 6, 10};
    int target = 16;
    memset(memo, -1, sizeof(memo));
    printf("Subset sum result: %s\n", subsetSum(arr, 4, target) ? "True" : "False");
    return 0;
}

---

 

Java 구현

백트래킹 코드

public class SubsetSum {
    public static boolean subsetSum(int[] arr, int n, int target) {
        if (target == 0) return true;
        if (n == 0 || target < 0) return false;

        return subsetSum(arr, n - 1, target - arr[n - 1]) || subsetSum(arr, n - 1, target);
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 10};
        int target = 16;
        System.out.println("Subset sum result: " + (subsetSum(arr, arr.length, target) ? "True" : "False"));
    }
}

메모이제이션 코드

import java.util.Arrays;

public class SubsetSum {
    private static int[][] memo;

    public static boolean subsetSum(int[] arr, int n, int target) {
        if (target == 0) return true;
        if (n == 0 || target < 0) return false;

        if (memo[n][target] != -1) return memo[n][target] == 1;

        boolean result = subsetSum(arr, n - 1, target - arr[n - 1]) || subsetSum(arr, n - 1, target);
        memo[n][target] = result ? 1 : 0;
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 10};
        int target = 16;
        memo = new int[arr.length + 1][target + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        System.out.println("Subset sum result: " + (subsetSum(arr, arr.length, target) ? "True" : "False"));
    }
}

---

 

Python 구현

백트래킹 코드

def subset_sum(arr, n, target):
    if target == 0:
        return True
    if n == 0 or target < 0:
        return False

    return subset_sum(arr, n - 1, target - arr[n - 1]) or subset_sum(arr, n - 1, target)

arr = [2, 4, 6, 10]
target = 16
print(f"Subset sum result: {subset_sum(arr, len(arr), target)}")

메모이제이션 코드

def subset_sum(arr, n, target, memo):
    if target == 0:
        return True
    if n == 0 or target < 0:
        return False

    if (n, target) in memo:
        return memo[(n, target)]

    memo[(n, target)] = subset_sum(arr, n - 1, target - arr[n - 1], memo) or subset_sum(arr, n - 1, target, memo)
    return memo[(n, target)]

arr = [2, 4, 6, 10]
target = 16
memo = {}
print(f"Subset sum result: {subset_sum(arr, len(arr), target, memo)}")

---

 

3. 성능 비교

실행 시간 비교 (Python 기준)

입력값	백트래킹 (초)	메모이제이션 (초)
4, 16	0.001	0.0001
20, 50	비효율적	0.01

---

 

4. 결론

• 백트래킹은 단순하지만 입력 크기가 커질수록 비효율적입니다.
• 메모이제이션은 중복 계산을 방지해 효율성을 크게 개선합니다.