[CS]완전 탐색(Brute Force)

Brute Force : 완전탐색

• brute[=무식한] + force[=힘]: 무식하게 해결하는 방법
• 가능한 모든 경우를 탐색하는 기법

Brute Force 효용성

• Brute Force 장점
  • 100% 답 도출 가능
• Brute Force 단점
  • 끔찍한 시간 복잡도(효율성)

Brute Force 종류

• 1. 선형 Brute Force : 순차탐색
  • 다중 for문을 통해 구현
• 2. 비 선형 Brute Force : DFS / BFS / 백트래킹 등
  • 각 알고리즘에 맞는 구현

Brute Force 예시

int change = 120, ways = 0, min = INF;
for(i = 0; i * 50 <= change; i = i + 1){
	for(j = 0; j * 10 <= change; j = j + 1){
		if( (i * 50) + (j * 10) = change) ways++;
		if(min > i+j) min = i+j;    	
    }
}