[알고리즘] Brute force 브루트포스 알고리즘 알아보기 ( 백준 2309번 일곱 난쟁이 with 자바 )

 

🤔 Brute force 브루트포스 알고리즘?

'무식한 힘' 으로 해석할 수 있겠습니다, 이 뜻 처럼 주어진 문제를 무식하게 하나하나 탐색하는 알고리즘 입니다.

모든 경우의 수를 전부 탐색하여 조건에 맞는 답을 찾기 때문에 정확한 답을 보장합니다.

하지만 모든 경우의 수를 탐색하기 때문에 시간복잡도가 높다는 단점이 있습니다.

그렇기 때문에 브루트포스 알고리즘은 시간복잡도를 고려하여 사용해야합니다.

또한 브루트포스 알고리즘은 정형화된 틀이 없기때문에 주어진 문제 유형에 따라 다양한 방법으로 풀이합니다.

• 단순 Brute force ( for문 )
• 재귀호출
• 비트마스크
• 순열
• DFS / BFS

 

💡 하지만 비효율적으로 보이는 브루트포스 알고리즘을 왜 사용할까요?

입력되는 범위가 작고, 탐색해야할 경우의 수가 적은 간단한 문제의 경우 최적화된 복잡한 알고리즘을 구현하는 비용이 높기때문에 직관적으로 모든 경우의 수를 구하는 쪽이 더 효율적일 수 있습니다.

또한 모든 경우를 탐색하여 답을 도출하므로 항상 정확한 답을 찾아낼 수 있는 강력한 방법이기도 합니다.

 

✔ 문제 유형

주어진 조건에 맞는 조합을 찾는 문제

 

✔ 문제 풀이

난이도 : 브론즈1 🥉

2309번: 일곱 난쟁이

 

9명의 난쟁이들 중 7명의 난쟁이들의 키의 합이 100이 되는 난쟁이들(조합)을 찾는 문제입니다.

 

브루트포스 알고리즘에는 여러가지 방법이 있지만 가장 간단한 반복문을 사용해서 직관적으로 모든 경우의 수를 탐색하여 문제를 풀어보겠습니다.

 

처음 문제를 접했을 때 난쟁이의 키를 한명씩 더하여 문제를 풀어나가려 했지만 7명의 조합을 만들어야 하기때문에 반복문을 많이 사용하게 됩니다.😭

그렇다면 반대로 9명의 난쟁이의 키중 2명의 난쟁이 키를 빼는식으로 접근한다면 2명의 난쟁이의 조합만 신경쓰면 될 것 입니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.lang.StringBuilder;
import java.util.Arrays;

public class Main{
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        
        int[] dwarfs = new int[9];
        int sum = 0;
        for( int i = 0; i<9; i++){
            dwarfs[i] = Integer.parseInt(br.readLine());
            sum += dwarfs[i]; // 9명의 난쟁이 키의 총 합을 구합니다.
        }

        for( int i = 0; i<8; i++){
            for( int j = i+1; j<9; j++){
            	/*
                * 2명의 난쟁이 키를 뺀 값이 100이라면 키를 0으로 변경함으로써 제외합니다
                * 정렬을 통해 제외한 값을 맨 앞으로 위치시키고 
                * index 2번 ( k = 2 ) 부터 난쟁이의 키를 출력합니다.
                */ 
                if( sum - dwarfs[i] - dwarfs[j] == 100){
                    dwarfs[i] = 0;
                    dwarfs[j] = 0;
                    Arrays.sort(dwarfs);
                    for( int k = 2; k<9; k++){
                        sb.append(dwarfs[k]).append("\n");
                    }
                    System.out.print(sb);
                    return;
                }
            }
        }
	}
}

 

📌 

브루트포스 알고리즘 문제 중 잘 알려진 블랙잭 문제처럼 고정된 조합을 구하기 때문에 그렇게 접근하려 했으나 조합의 범위가 많아 한번 더 생각 해야하는 문제 같습니다.

DFS알고리즘과 같은 재귀호출을 통해서도 해결할 수 있지만 재귀에대한 이해가 조금 부족한것 같아 직관적인 for문을 통해 풀어보았습니다.