[CODE-STATES-BE] SEC-2 [알고리즘,자료구조] 재귀 , 그래프 이론 약간 DFS

유형찬·2022년 9월 20일

Java 알고리즘 자료구조 자바

Code States

목록 보기

9/21

재귀

재귀란 함수가 자기 자신을 호출하는 것을 말한다.

재귀는 반복문을 사용하지 않고도 반복을 구현할 수 있다는 장점이 있다.

하지만 재귀는 함수를 호출하는 과정에서 스택에 쌓이는데,

이는 메모리를 많이 사용하고

함수 호출 횟수가 많아지면 스택 오버플로우가 발생할 수 있다는 단점이 있다.

그래서 재귀는 최대한 사용하지 않는 것이 좋다.

그렇다면 언제 사용?

위에서는 최대한 사용하지 않는 것이 좋다고 했다. 그렇다면 언제 사용하는 것이 좋을까?

재귀는 순환적인 구조를 표현할 때 사용한다.

예를 들어, 트리 구조를 표현할 때, 재귀를 사용하면 편리하다. 이는 후반부 DFS를 다룰 때 자세히 다루도록 하겠다.

순환적 구조란 자기 자신을 포함하고 다시 자기 자신을 포함하는 구조를 말한다.

예를 들어, 피보나치 수열을 구하는 함수를 재귀로 구현하면 다음과 같다.

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

실행 결과

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 8

위 코드를 보면, fibonacci 함수가 자기 자신을 호출하고 있다.

이는 fibonacci 함수가 순환적인 구조를 가지고 있기 때문이다.

재귀의 종료 조건

재귀 함수를 사용할 때는 종료 조건을 반드시 명시해야 한다.

종료 조건이 없다면, 함수가 무한히 호출되어 스택 오버플로우가 발생할 수 있다.

재귀가 어려운 이유가 바로 이것 때문이다.

예시를 한 번 살펴보자.

public static void recursive(int n) {
    System.out.println(n);
    recursive(n + 1);
}

위 코드는 재귀 함수이다.

하지만, 종료 조건이 없기 때문에 무한히 호출된다. 따라서 다음 오류를 반환한다.

StackOverflowError

이를 해결하기 위해서는 종료 조건을 명시해야 한다.

public static void recursive(int n) {
    if (n == 100) {
        return;
    }
    System.out.println(n);
    recursive(n + 1);
}

재귀의 성능

재귀 함수는 함수 호출 횟수가 많아지면 성능이 떨어진다.

재귀의 성능이 떨어지는 이유는 함수 호출 시 스택에 쌓이는 비용 문제도 있지만

중복 연산이 발생하기 때문이다.

예를 들어, 피보나치 수열을 구하는 함수를 재귀로 구현하면 다음과 같다.

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

피보나치 수열을 구하는 함수는 다음과 같이 재귀 호출이 두 번 일어난다.

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)

위 코드를 보면, fibonacci(2)가 두 번 호출되었다.

이는 중복 연산이 발생한 것이다.

이를 해결하기 위해서는 메모이제이션을 사용하면 된다.

메모이제이션

메모이제이션은 동적 계획법 을 구현하는 방법 중 하나이다.

다이나믹 프로그래밍이라고도 불리며 보통 DP라고 줄여서 부른다.
최적 부분 구조와 중복되는 부분 문제를 가지고 있을 때 사용할 수 있다.
하향식 접근법으로 상향식 접근법보다 빠르게 동작한다.
메모이제이션을 이용해 중복되는 연산을 제거한다.
메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
동적 계획법은 메모이제이션을 포함하는 개념이다.

메모제이션의 예

피보나치 수열을 구하는 함수를 메모이제이션을 이용해 구현하면 다음과 같다.

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

위 코드를 보면, fibonacci(2)가 한 번만 호출되었다.

이는 메모이제이션을 이용해 중복 연산을 제거했기 때문이다.

피보나치 수열의 시간 복잡도

메모이제이션을 이용해 피보나치 수열을 구하는 함수의 시간 복잡도는 다음과 같다.

시간 복잡도: O(N)
공간 복잡도: O(N)

메모제이션을 이용하지 않은 일반 재귀 함수의 시간 복잡도는 다음과 같다.

시간 복잡도: O(2^N)
공간 복잡도: O(N)
N이 커질수록 시간 복잡도가 기하급수적으로 증가한다.
N이 40이 넘어가면 이미 1초 이상의 시간이 소요된다.
N이 45가 넘어가면 이미 1분 이상의 시간이 소요된다.
N이 50이 넘어가면 이미 1시간 이상의 시간이 소요된다.
N이 60이 넘어가면 이미 1년 이상의 시간이 소요된다.
N이 70이 넘어가면 이미 1세기 이상의 시간이 소요된다.
N이 80이 넘어가면 이미 1만년 이상의 시간이 소요된다.
N이 90이 넘어가면 이미 1억년 이상의 시간이 소요된다.

그래프에서 재귀 함수의 활용

DFS(Depth-First Search)

깊이 우선 탐색이라고도 부른다.
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
스택 자료구조(혹은 재귀 함수)를 이용한다.
구체적인 동작 과정
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
4. DFS 스택 자료구조의 성질을 이용하는 알고리즘이다.
5. DFS 노드의 수가 V개일 때, O(V)의 시간이 소요된다.
6. DFS 노드의 수가 V개이고 간선의 수가 E개일 때, O(V+E)의 시간이 소요된다.
7. DFS 인접 리스트 방식으로 그래프를 표현할 때, 노드의 수가 V개이고 간선의 수가 E개일 때, O(V+E)의 시간이 소요된다.
8. DFS 인접 행렬 방식으로 그래프를 표현할 때, 노드의 수가 V개이고 간선의 수가 E개일 때, O(V^2)의 시간이 소요된다.

구체적인 설명은 여기를 참고하자.

BFS 와 DFS 그래프 이론은 다음에 자세히 것으로 하고 넘어가자.

그래서 BFS 에서 재귀를 이용한 예를 보면

public class Main {
    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y])
                dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);

        // 노드 2에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(2).add(1);
        graph.get(2).add(7);

        // 노드 3에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);

        // 노드 4에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(4).add(3);
        graph.get(4).add(5);

        // 노드 5에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(5).add(3);
        graph.get(5).add(4);

        // 노드 6에 연결된 노드 정보 저장 (노드, 노드)
        graph.get(6).add(7);

        // 노드 7에
[...]
    
            // 노드 8에 연결된 노드 정보 저장 (노드, 노드)
            graph.get(8).add(1);
            graph.get(8).add(7);
    
            dfs(1);
        }
    }