[Combination]- Java코드 (DFS, BFS 방식 -성능비교)

알고리즘 문제를 풀때, 

조합 개념이 요구되는 경우가 많이 존재한다.

조합을 구현하는 범용적인 두가지 방법을 익혀 코테와 실무에서 직접 코딩하기 위해 정리한다.

input 으로 들어온  문자열에서  문자 n개 중 r개를 선택하는 경우의 값을 배열에 저장해 반환하는 코드를 만들어보겠다.

 

 

1. 백트레킹 방법 

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

조합에서 백트레킹은 한 요소마다 선택과, 비선택 두가지의 경우로 진행됩니다.

 

    // 사용 예시 : 문자열 값, 선택여부 체크 배열 chosen, 시작위치 start, 전체개수 n, 앞으로 선택할 개수 r)
    static void combination_DFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }
        if(start == n)
        	return;
    	chosen[start] = true;
        combinationFunc(arr, chosen, start + 1, n, r - 1); // start를 선택한 경우
        chosen[start] = false;
        combinationFunc(arr, chosen, start + 1, n, r); // start를 선택 안한 경우
    }
    // 배열 출력
    static void print(String arr, boolean[] chosen, int n) {
        for (int i = 0; i < n; i++) 
            if (chosen[i]) 
                System.out.print(arr.charAt(i) + " ");            
        System.out.println();
    }

 

2. 재귀 방법 - BFS

    // 사용 예시 : 문자열 값, 선택여부 체크 배열 chosen, 시작위치 start, 전체개수 n, 앞으로 선택할 개수 r)
    static void combinationF_BFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }

        for (int i = start; i < n; i++) {
            chosen[i] = true;
            combinationFunc(arr, chosen, i + 1, n, r - 1);
            chosen[i] = false;
        } 
    }	
    // 배열 출력
    static void print(String arr, boolean[] chosen, int n) {
        for (int i = 0; i < n; i++) 
            if (chosen[i]) 
                System.out.print(arr.charAt(i) + " ");            
        System.out.println();
    }

 

 

3. 전체 코드, 효율성 비교

package week2;
// dfs - 넓이우선 재귀호출
public class combination_dfs {
	public static void main(String[] args) {
		System.gc(); 
		// 실행전 메모리 사용량 조회
		long before = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
		// 시작시간 기록
		long start = System.currentTimeMillis(); 
		
        String arr = "abcdefghijk"; 
        int n = arr.length(); 
        boolean[] chosen = new boolean[n];
        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            combination_DFS(arr, chosen, 0, n, i);
        }
        
        long after = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        System.out.println("\n\n사용메모리 : "+(after - before)/1024 + " KB");
        long end = System.currentTimeMillis();
        System.out.println("실행시간 : " + (end - start)/1000.0);
        
    }
    
    static void combination_DFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }
        if(start == n)
        	return;
    	chosen[start] = true;
    	combination_DFS(arr, chosen, start + 1, n, r - 1);
        chosen[start] = false;
        combination_DFS(arr, chosen, start + 1, n, r);
    }
   
   	static void combination_BFS(String arr, boolean[] chosen, int start, int n, int r) {
        if (r == 0) {
            print(arr, chosen, n);
            return;
        }

        for (int i = start; i < n; i++) {
        	chosen[i] = true;
        	combination_BFS(arr, chosen, i + 1, n, r - 1);
            chosen[i] = false;
        } 
    }	
    // 배열 출력
    static void print(String arr, boolean[] chosen, int n) {
        for (int i = 0; i < n; i++) 
            if (chosen[i]) 
                System.out.print(arr.charAt(i) + " ");            
        System.out.println();
    }
}

처음에는 두가지 방법 모두 함수내에서 재귀적으로 호출하여 구분이 의미가 있나 싶었지만,

둘의 구현방식 자체가 깊이우선 호출이냐, 넓이 우선 방식이냐의 차이였기에,

사용하는 메모리와 실행속도가 정 반대의 결과를 가져왔다.

 

DFS방식

사용메모리 : 420 KB
실행시간 : 0.201

BFS 방식

사용메모리 : 705 KB
실행시간 : 0.147

 

백트레킹은 함수한번에 두번의 호출이 일어나므로 2의 제곱수 많큼 깊어지면서 함수가 실행이되므로,

재귀방식에 비해 속도가 상대적으로 느리고, 메모리 사용이 적으며, 

재귀호출의 경우, 반복문을 통해 함수한번에 N번만큼의 호출이 일어나므로 한 사이클당 N의 제곱수만큼 실행됩니다.

상대적으로 속도가 빠르고, 메모리를 많이 사용합니다.

 

둘의 차이가 궁금해서 탐구해보았는데, DFS와 BFS의 차이점을 정리하는 시간이 되었습니다.