Stack(2) - DP(동적 계획법), DFS(깊이우선탐색)

DP (동적 계획법)

DP란 Dynamic Programming의 약자이며 최적화 문제를 해결하는 알고리즘 설계기법 중 하나이다. 

• 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제를 해결한다
• 최종적으로 원래 주어진 입력의 문제를 해결한다

즉 점층적으로 문제를 해결해나가는 방식이다. 

앞선 예제인 피보나치 수열을 DP 방식으로 해결해보자. 

• 문제를 부분 문제로 분할한다
• F(N) = F(N-2) + F(N-1)
• F(N-1) = F(N-3) + F(N-2)
• ...
• F(3) = F(2) + F(1)
• 부분 문제로 나누는 일이 끝났으면 작은 부분부터 해를 구한다.
• F(2) = 1, F(1) = 1 이다
• 부분 문제의 해를 이용하여 전체의 해를 구한다.
• F(2)와 F(1)을 이용하여 전체의 해를 구한다.

보통 Memorization는 재귀적 구조에 사용하는 것보다 반복문에서 사용하는 것이 효율적이다. 재귀 함수에서는 스택 오버플로우가 발생할 수 있다.

DP구현 - 피보나치 수열 ( 재귀함수 )

public class FibonacciNumberDP {
    private static Integer[] fArr; 
    public static void main(String[] args) {
        fArr = new Integer[46];
        fArr[0] = 0;
        fArr[1] = 1;
        fArr[2] = 1;
        
        int number = getFibonacciNumber(45);
        System.out.println(number);
    }
    
    public static int getFibonacciNumber(int index) {
        if(fArr[index] != null) {
            return fArr[index];
        }
        
        fArr[index] = getFibonacciNumber(index-2) + getFibonacciNumber(index-1);
        return fArr[index];
    }
}
 

DP구현 - 피보나치 수열 (반복문)

public class FibonacciNumberDP2 {
    private static Integer[] fArr; 
    public static void main(String[] args) {
        fArr = new Integer[46];
        fArr[0] = 0;
        fArr[1] = 1;
        fArr[2] = 1;
        
        for(int i=3; i<46; i++) {
            fArr[i] = fArr[i-2] + fArr[i-1];
        }
        int result = fArr[45];
        System.out.println(result);
    }
}
 

DFS(깊이우선탐색)

비선형구조인 그래프 구조를 검색하는 두 가지 방법 중 하나이다. 

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색한다
• 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아온다
• 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문, 순회한다

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선탐색을 반복해야 하므로 후입선출 구조의 Stack을 사용하는게 적절하다.

DFS를 구현해보자

import java.util.EmptyStackException;
import java.util.Stack;
 
public class DFS_깊이우선탐색 {
    public static boolean[] visitedArr = new boolean[7];
    
    public static void main(String[] args) {
        // 탐색 정점 표시 a,b,c,d,e,f 방문표시
        for(int i=0; i<visitedArr.length; i++) {
            visitedArr[i] = false;
        }
        // 그래프 연결
        
        Data g = new Data("g", 6, null);
        Data f = new Data("f", 5, g);
        Data e = new Data("e", 4, f);
        Data d = new Data("d", 3, f);
        Data c = new Data("c", 2, e);
        Data b = new Data("b", 1, d, e);
        Data a = new Data("a", 0, b, c);
        
        // 정점 스택
        Stack<Data> dataStack = new Stack<>();
 
        try {
            // 순회 시작점 a
            Data start = a;
            do {
                start.visit();
                
                // 방문하지않은 정점 찾기
                Data unvisit = start.getNotVisit();
                if(unvisit != null) {
                    dataStack.push(start);
                } 
                System.out.println("[정점]:"+start.getName()+"->");
                
                while(unvisit != null) {
                    System.out.println("\t[방문 정점]:"+unvisit.getName());
                    unvisit.visit();
                    // 방문하지 않은 정점찾기
                    if(unvisit.getNotVisit() != null) {
                        dataStack.push(unvisit);
                        unvisit = unvisit.getNotVisit();
                    } else {
                        unvisit = null;
                    }
                }
                start = dataStack.pop();
            } while(start != null);
        } catch(EmptyStackException e1) {
            // 방문결과확인
            for(int i=0; i<visitedArr.length; i++) {
                System.out.println(visitedArr[i]);
            }
        }
        
    }
}
 
class Data {
    private String name;
    private int index;
    private Data[] links;
    
    public Data(String name, int index, Data... data) {
        this.name = name;
        this.index = index;
        this.links = data;
    }
    
    public String getName() {
        return this.name;
    }
    
    public void visit() {
        DFS_깊이우선탐색.visitedArr[index] = true;
    }
    
    public boolean isVisit() {
        return DFS_깊이우선탐색.visitedArr[index];
    }
    
    public Data getNotVisit() {
        Data unvisit = null;
        
        if(links == null) {
            return null;
        }
        
        for(int i=0; i<links.length; i++) {
            Data link = links[i];
            if(!link.isVisit()) {
                unvisit = link;
                break;
            }
        }
        return unvisit;
    }
}