인프런 JAVA 알고리즘 정리(DFS, BFS 기초 1~6번)

1. 재귀함수 (스택프레임)

public static void DFS(int n){
    if(n==0){
    }else {
        DFS(n-1);
        System.out.println(n);
    }
}

 

 

2. 10진수를 2진수로 (재귀사용)

public static void DFS(int n){
    if(n==0){
    }else {
        DFS(n/2);
        System.out.print(n%2);
    }
}

 

3. 팩토리얼

public static int DFS(int n){
    if(n==0){
        return 1;
    }else {
        return n*DFS(n-1);
    }
}

 

4. 피보나치 ( 재귀 + 메모리제이션 )

public class Main {
    static int[] arr;
    public static void main(String[] args) {
        int n = 10;
        arr = new int[n+1];
        System.out.println(DFS(n));
        for(int i=1; i<arr.length; i++){
            System.out.print(arr[i]+" ");
        }
    }
    public static int DFS(int n){
        if(n==1 || n==2){
            arr[n] = 1;
            return 1;
        }else{
            // 재귀를 통해 이미 구해진 값이면 굳이 다시 재귀 x
            // 메모리제이션 
            if(arr[n]==0) arr[n] = DFS(n-1)+DFS(n-2);
            return arr[n];
        }
    }
}

- 재귀는 스택 프레임에 복귀주소, 지역변수등이 저장되면서 반복을 하기 때문에 일반적으로 for문에 비해 성능이 안 좋음

 

 

5. 이진트리순회 (DFS)

- 전위순회

- 중위순회

- 후위순회 

 

 

6. 부분집합 구하기 (DFS)

- 사용한다 안한다로 구별 = 2개의 DFS함수를 통하여 재귀

- 마지막 if문에서 결과 출력

public class Main {
    static int[] ch;
    static int n;
    public static void main(String[] args) {
        n = 3;
        ch = new int[n+1];
        DFS(1); // 1부터 시작해서 3까지의 경우의 수
    }
    public static void DFS(int L){
        if(L==n+1){ 
            String tmp = "";
            for(int i=1; i<=n; i++){
                if(ch[i]==1) tmp+=(i+" ");
            }
            if(tmp.length()>0) System.out.println(tmp);
        }else{
            ch[L]=1; // 사용한다.
            DFS(L+1);
            ch[L]=0; // 사용하지 않는다.
            DFS(L+1);
        }
    }
}