메모이제이션(Memoization) 적용을 통한 성능 개선 (1) - 브루트포스

메모이제이션을 통한 브루트포스 성능 개선

 

반응형

 프로그래밍 문제를 해결하는 데 있어 브루트포스(완전 탐색)는 간단하면서도 강력한 접근 방식입니다. 하지만 입력 크기가 커지면 성능 문제가 발생하기 마련입니다. 이를 해결하기 위해 메모이제이션(Memoization)이라는 기술을 적용하면 효율성을 극대화할 수 있습니다. 이번 글에서는 브루트포스와 메모이제이션의 차이를 살펴보고, C언어, Java, Python으로 각각 메모이제이션을 적용한 예제를 통해 메모이제이션의 강력함을 확인하겠습니다.

---

 

1. 브루트포스와 메모이제이션이란?

브루트포스(완전 탐색)

• 가능한 모든 경우를 탐색하며 답을 찾는 방식입니다.
• 단순하지만, 경우의 수가 많아지면 계산량이 폭발적으로 증가합니다.

메모이제이션

• 한 번 계산한 결과를 저장해둠으로써 동일한 계산을 반복하지 않도록 하는 기법입니다.
• 중복 계산을 방지하여 성능을 향상시킵니다.

브루트포스와 메모이제이션에 대한 자세한 설명은 아래 글들을 참고하면 좋습니다.

2024.12.20 - [알고리즘] - 브루트포스(Brute Force) 알고리즘 완벽 가이드 - 완전탐색, 코딩테스트 빈출개념, 주의사항, 원리, C, Java, Python 예시코드

브루트포스(Brute Force) 알고리즘 완벽 가이드 - 완전탐색, 코딩테스트 빈출개념, 주의사항, 원리, C

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

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

 

---

 

2. 피보나치 수열 문제를 통해 비교하기

피보나치 수열은 대표적인 메모이제이션 적용을 통해 완전탐색의 성능을 개선할 수 있는 문제입니다.  아래에서 브루트포스와 메모이제이션을 각각 적용한 코드를 살펴보겠습니다.

 

C 언어 구현

브루트포스 코드

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 40; // 예제 입력
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    return 0;
}

메모이제이션 코드

#include <stdio.h>

int memo[100] = {0};

int fibonacci(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n = 40; // 예제 입력
    printf("Fibonacci(%d) = %d\n", n, fibonacci(n));
    return 0;
}

---

 

Java 구현

브루트포스 코드

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 40; // 예제 입력
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
    }
}

메모이제이션 코드

public class Fibonacci {
    private static int[] memo = new int[100];

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 40; // 예제 입력
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
    }
}

---

 

Python 구현

브루트포스 코드

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

n = 40  # 예제 입력
print(f"Fibonacci({n}) = {fibonacci(n)}")

메모이제이션 코드

def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

n = 40  # 예제 입력
print(f"Fibonacci({n}) = {fibonacci(n)}")

---

 

3. 성능 비교

계산량 비교

• 브루트포스: 계산 시 중복 호출이 매우 많아 시간이 오래 걸립니다.
• 메모이제이션: 이미 계산된 결과를 재사용하여 계산량이 크게 줄어듭니다.

실행 시간 비교 (Python 기준)

입력값	브루트포스 (초)	메모이제이션 (초)
30	0.1	0.0001
40	25.5	0.0002

---

 

4. 결론

• 브루트포스는 간단하지만 비효율적이며, 입력 크기가 커질수록 사용하기 어렵습니다.
• 메모이제이션은 중복 계산을 방지하여 성능을 획기적으로 개선할 수 있습니다.