[알고리즘 기법] 완전탐색 ( 브루트 포스 : Brute-Force )

 

◇  설명

  ◎  ‘무식하게 푼다( brute-force )’ (전산학) 
    : 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미

  ◎  완전 탐색 ( exhaustive search )
    :  가능한 방법을 전부 만들어 보는 알고리즘
   -  컴퓨터가 속도가 빠르다는 장점을 가장 잘 이용하는 방법
   -  손으로 직접 풀기에는 경우의 수가 많을 때 충분히 빠르면서도 가장 구현하기 쉬운 수단이 됨
   -  어떻게 쉽게 푸는 방법이 없을까 고민할 필요 없이, 무식하지만 훨씬 간편하게 문제를 풀어낼 수 있음.
   -  완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법
   -  재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구
  ※  최적화 문제  :  문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 ‘좋은’ 답을 찾아내는 문제들
                          ( 최솟값, 최댓값 등 )

  ◎  완전 탐색 레시피
   1.  완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례함.  
       최대 크기 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있는지 가늠.
   2.  가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눔. 각 선택은 답의 후보를 만드는 과정의 한 조각이 됨
   3.  그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성
   4.  조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성 했으므로, 이것을 기저 사례로 선택해 처리

 

◇  코드

  ex)  순열

public class Recursion_permutation {
	
	static char data[] = { 'a', 'b', 'c', 'd' };
	static int n = data.length;
	
	public static void swap( char[] data, int k, int i ) {
		char tmp;
		tmp = data[k];
		data[k] = data[i];
		data[i] = tmp;
	}

	public static void perm( char[] data, int k, int n ) {
		if( k == n ) {
			for( int i = 0; i < n; i++ )
				System.out.print( data[i] + " " );
			System.out.println();
			return;
		}
		for( int i = k; i < n; i++ ) {
			swap( data, k, i );
			perm( data, k+1, n );
			swap( data, k, i );
		}
	}

	public static void main(String[] args) {
		
		perm( data, 0, n );
	}
}

 

◇  출처

  -  설명  --  알고리즘 문제 해결 전략 ( 구종만 )
  -  코드  --  영리한 프로그래밍 ( 권오흠 )