브루트포스 알고리즘 - Brute Force

브루트 : 무식한

명칭처럼 무식하게 탐색하는 알고리즘이다.

 

문제를 해결하기 위해 모든 경우의 수를 확인해본다 라고 생각하면된다.

그럼 완전탐색 알고리즘과 백트레킹 알고리즘과 거의 유사해 보이지만, 브루트포스는 그냥 완전히 확인하는 것이라 생각하면 된다.

 

모든 경우의 수를 확인하는 점은 최적의 결과를 반환시켜 주지만, 반대로 시간이 오래걸린다는 점이 단점이 된다.

 

브루트포스 : 모든 탐색을 진행

완전탐색 : 모든 탐색을 진행하지만 가능하다면 조건을 활용해 불필요한 탐색을 제거

백트레킹 : 명확한 조건을 두어, 불필요한 탐색을 제거하는 가지치기 방식

 

예시 문제

https://www.acmicpc.net/problem/2798

주어지는 카드들로 3장의 카드를 골라서 주어지는 값에 가장 근접하게 만들어 내야한다.

대신 반드시 3장의 카드를 사용해서 조합한 결과값이여야 하며, 결과값을 넘지 말아야 한다.

 

풀이

namespace BOJ_2798
{
    // 24/11/09
    // 문제 : BOJ 2789
    // URL : https://www.acmicpc.net/problem/2798

    internal class Program
    {
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int[] cards = new int[input[0]];
            int target = input[1];

            input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            for (int i = 0; i < input.Length; i++)
            {
                cards[i] = input[i];
            }

            int sum = 0;

            sum = Find(cards, 0, 0, 0,target);

            Console.WriteLine(sum);
        }

        static int Find(int[] cards, int idx, int selectCount, int currentSum, int target)
        {
            if (selectCount == 3)
            {
                return currentSum <= target ? currentSum : -1;
            }

            int maxSum = -1;

            for (int i = idx; i < cards.Length; i++)
            {
                int result = Find(cards, i + 1, selectCount + 1, currentSum + cards[i], target);
                
                if (result != -1)
                {
                    maxSum = Math.Max(maxSum, result);
                }
            }

            return maxSum;
        }

    }
}