메모이제이션을 통한 성능개선 (3) - DFS

DFS 성능 개선

 

반응형

 

DFS(Depth First Search)는 그래프 탐색 및 다양한 문제를 해결하는 데 널리 사용되는 알고리즘입니다. 이 알고리즘에 메모이제이션(Memoization)을 활용하면 중복 계산을 제거하고 효율성을 극대화할 수 있습니다. 이번 포스팅에서는 DFS와 메모이제이션의 결합 아이디어를 설명하고, C, Java, Python 예제 코드와 함께 성능 비교를 통해 차이를 분석하겠습니다.

---

1. DFS와 메모이제이션이란?

DFS (Depth First Search)

• 깊이 우선 탐색으로, 그래프의 한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색합니다.
• 백트래킹과 결합하여 다양한 문제를 해결할 수 있습니다.

메모이제이션

• 계산한 값을 저장하여 동일한 계산을 반복하지 않도록 하는 기술입니다.
• DFS와 결합하면 중복된 상태를 다시 탐색하지 않음으로써 성능을 크게 개선할 수 있습니다.

 

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

2024.12.19 - [알고리즘] - DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도

DFS (깊이 우선 탐색, Depth-First Search) 알고리즘 - C언어, Java, Python 예시코드, 시간복잡도

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

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

 

 

---

 

2. 예제 문제: 계단 오르기 문제

계단의 최상단에 도달하는 방법의 수를 구하는 문제를 생각해보겠습니다. 한 번에 1계단 또는 2계단만 오를 수 있을 때, 계단을 오르는 방법의 수를 구합니다.

---

 

3. 구현 코드

C 언어 구현

DFS만 사용한 코드

#include <stdio.h>

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

int main() {
    int n = 4;
    printf("Number of ways: %d\n", dfs(n));
    return 0;
}

메모이제이션 적용 코드

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

int memo[100];

int dfs(int n) {
    if (n == 0) return 1;
    if (n < 0) return 0;
    if (memo[n] != -1) return memo[n];

    return memo[n] = dfs(n - 1) + dfs(n - 2);
}

int main() {
    int n = 4;
    memset(memo, -1, sizeof(memo));
    printf("Number of ways: %d\n", dfs(n));
    return 0;
}

 

Java 구현

DFS만 사용한 코드

public class Staircase {
    public static int dfs(int n) {
        if (n == 0) return 1;
        if (n < 0) return 0;
        return dfs(n - 1) + dfs(n - 2);
    }

    public static void main(String[] args) {
        int n = 4;
        System.out.println("Number of ways: " + dfs(n));
    }
}

메모이제이션 적용 코드

import java.util.Arrays;

public class Staircase {
    private static int[] memo;

    public static int dfs(int n) {
        if (n == 0) return 1;
        if (n < 0) return 0;
        if (memo[n] != -1) return memo[n];

        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 4;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        System.out.println("Number of ways: " + dfs(n));
    }
}

 

 

Python 구현

DFS만 사용한 코드

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

n = 4
print(f"Number of ways: {dfs(n)}")

메모이제이션 적용 코드

def dfs(n, memo):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if n in memo:
        return memo[n]

    memo[n] = dfs(n - 1, memo) + dfs(n - 2, memo)
    return memo[n]

n = 4
memo = {}
print(f"Number of ways: {dfs(n, memo)}")

---

 

4. 성능 비교

실행 시간 비교 (Python 기준)

입력값	DFS (초)	메모이제이션 (초)
10	0.002	0.0001
20	0.05	0.0002
30	1.2	0.0003
40	계산 불가	0.0004

분석

1. DFS만 사용하면 중복된 계산이 많아 입력 크기가 커질수록 성능이 급격히 저하됩니다.
2. 메모이제이션은 계산된 값을 저장하여 재사용함으로써 성능을 크게 개선합니다.
3. 메모이제이션은  매우 큰 입력값에서도 빠르게 처리할 수 있습니다.

---

 

5. 결론

• DFS는 직관적이지만 중복 계산으로 인해 비효율적일 수 있습니다.
• 메모이제이션은 중복 계산을 제거하여 효율성을 극대화합니다.