Brute Force

Brute Force(무차별 대입)

brute force 방법은 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방식입니다. 이 방식은 일반적으로 효율성이 떨어질 수 있지만, 모든 경우를 체크하기 때문에 정확한 답을 찾을 수 있습니다.

1. 접근 방법: 가능한 모든 조합을 생성하거나 탐색합니다.
2. 효율성: 일반적으로 느리며, 복잡도가 높을 수 있습니다. 대부분의 경우, 시간 복잡도는 O(n!) 또는 O(2^n)입니다.
3. 적용 분야: 정확한 답이 필요하고, 입력 크기가 작은 경우에 사용할 수 있습니다.

예

두 숫자 중 두 개를 선택하여 합이 목푯값과 같은 경우를 찾는 예시 코드입니다.

 

Python

def findSumPairBruteForce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

numbers = [2, 4, 7, 11, 15]
target_sum = 9
print(findSumPairBruteForce(numbers, target_sum))  # True

 

관련 문제 1

정수로 이루어진 두 리스트가 주어집니다. 왼쪽 리스트에서 하나의 숫자를 선택하고, 오른쪽 리스트에서 하나의 숫자를 선택하여 두 수를 곱했을 때, 가장 작은 곱을 구하시오.

 

해답

함수 min_product는 리스트 left_numbers와 리스트 right_numbers를 파라미터로 받습니다. left_numbers는 왼쪽 리스트의 숫자들, right_numbers는 오른쪽 리스트의 숫자들이 담겨 있고, min_product는 left_numbers에서 숫자 하나와 right_numbers에서 숫자 하나를 뽑아서 곱했을 때 그 값이 최소가 되는 값을 리턴합니다.

def min_product(left_list: list, right_list: list) -> int:
    min_result = float("inf")
    for left in left_list:
        for right in right_list:
            current_result = left * right
            min_result = min(min_result, current_result)
    return min_result


# 테스트 코드
if __name__ == "__main__":
    print(min_product([1, 3, 4], [3, 4, 5]))    # 3
    print(min_product([-3, 4, -9], [3, -2, 1])) # -27

위의 코드는 주어진 두 리스트에서 각각 하나의 숫자를 선택하여 곱을 구하고, 그중에서 가장 작은 곱을 찾는 방식으로 문제를 해결합니다. 위의 예시 입력에 대해서는 가장 작은 곱을 구할 수 있습니다.

Java

public class ProductCalculator {  
    public static int minProduct(int[] leftList, int[] rightList) {  
        int minResult = Integer.MAX_VALUE;  
        for (int left : leftList) {  
        for (int right : rightList) {  
            int currentResult = left * right;  
            minResult = Math.min(minResult, currentResult);  
        }  
    }  
    return minResult;  
}  

    public static void main(String[] args) {  
        int[] leftList = {1, 3, 4};  
        int[] rightList = {3, 4, 5};  
        System.out.println(minProduct(leftList, rightList)); // 3  

        int[] leftList2 = {-3, 4, -9};  
        int[] rightList2 = {3, -2, 1};  
        System.out.println(minProduct(leftList2, rightList2)); // 27  
    }  
}

 

관련 문제 2

좌표 리스트에서 거리가 가장 먼 두 2차원 좌표를 찾으시오.
주어진 2차원 좌표 리스트에서 거리가 가장 먼 두 좌표를 찾아서 그 좌표 쌍을 반환하는 함수 farthest_coordinates(coordinates)를 작성하세요. 각 좌표는 튜플로 주어지며, x와 y 좌표값은 양의 정수로 가정합니다.

def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    # 코드 구현  


if __name__ == "__main__":  
    test_coordinates = [(4, 1), (1, 30), (34, 50), (5, 3), (13, 19), (32, 4)]  
    print(farthest_coordinates(test_coordinates))

 

 

해답

두 점 사이의 거리

두 점 사이의 거리는 아래 공식을 통해서 구할 수 있습니다.

distance = √((x₂ - x₁)² + (y₂ - y₁)²)

이를 코드화하면 아래와 같습니다.

from math import sqrt

sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)

그리고 이 거리를 구하는 코드는 반복해서 사용해야 하기에 아래처럼 메서드로 분리합니다.

def distance(coord1: tuple[int, int], coord2: tuple[int, int]) -> float:
    return sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)

최댓값 구하기

이중 루프를 통해 각각의 좌표 쌍의 거리를 계산하면서, 현재까지 가장 먼 거리를 갖는 좌표 쌍과 거리를 업데이트합니다.

def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    farthest_pair: list[tuple[int, int]] = [coordinates[0], coordinates[1]]  
    max_distance: float = distance(coordinates[0], coordinates[1])  

    for i in range(len(coordinates) - 1):  
        for j in range(i + 1, len(coordinates)):  
            coord1: tuple[int, int] = coordinates[i]  
            coord2: tuple[int, int] = coordinates[j]  
            cur_distance: float = distance(coord1, coord2)  

            if cur_distance > max_distance:  
                farthest_pair = [coordinates[i], coordinates[j]]  
                max_distance = cur_distance  

    return farthest_pair

 

python

from math import sqrt  


def distance(coord1: tuple[int, int], coord2: tuple[int, int]) -> float:  
    return sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)  


def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    farthest_pair: list[tuple[int, int]] = [coordinates[0], coordinates[1]]  
    max_distance: float = distance(coordinates[0], coordinates[1])  

    for i in range(len(coordinates) - 1):  
        for j in range(i + 1, len(coordinates)):  
            coord1: tuple[int, int] = coordinates[i]  
            coord2: tuple[int, int] = coordinates[j]  
            cur_distance: float = distance(coord1, coord2)  

            if cur_distance > max_distance:  
                farthest_pair = [coordinates[i], coordinates[j]]  
                max_distance = cur_distance  

    return farthest_pair  


if __name__ == "__main__":  
    test_coordinates = [(4, 1), (1, 30), (34, 50), (5, 3), (13, 19), (32, 4)]  
    print(farthest_coordinates(test_coordinates))  # [(4, 1), (34, 50)]

java

public class FarthestCoordinates {  
    public static double distance(int[] coord1, int[] coord2) {  
        return Math.sqrt(Math.pow(coord1[0] - coord2[1], 2) + Math.pow(coord1[1] - coord2[1], 2));  
    }  

    public static int[][] farthestCoordinates(int[][] coordinates) {  
        int[][] farthestPair = {coordinates[0], coordinates[1]};  
        double maxDistance = distance(coordinates[0], coordinates[1]);  

        for (int i = 0; i < coordinates.length - 1; i++) {  
            for (int j = i + 1; j < coordinates.length; j++) {  
                int[] coord1 = coordinates[i];  
                int[] coord2 = coordinates[j];  
                double curDistance = distance(coord1, coord2);  

                if (curDistance > maxDistance) {  
                    farthestPair[0] = coordinates[i];  
                    farthestPair[1] = coordinates[j];  
                    maxDistance = curDistance;  
                }  
            }  
        }  

        return farthestPair;  
    }  

    public static void main(String[] args) {  
        int[][] testCoordinates = {{4, 1}, {1, 30}, {34, 50}, {5, 3}, {13, 19}, {32, 4}};  
        int[][] result = farthestCoordinates(testCoordinates);  
        for (int[] coord : result) {  
            System.out.print("(" + coord[0] + ", " + coord[1] + ") ");  
        }  
        // (4, 1) (34, 50)
    }  
}