TIL-2024.02.17 - 알고리즘 - 완전 탐색 알고리즘 (Brute Force)

 

------- 완전 탐색 알고리즘 ? 

• 문제의 가능한 모든 경우의 수를 체계적으로 생성하고 검사하여, 문제의 해답을 찾는 방식입니다.
• 복잡한 알고리즘을 적용하기 전에 문제 해결의 가능성을 탐색하거나, 문제의 규모가 작을 때 유용하게 사용됩니다.

 

장점:

• 구현이 비교적 간단하고 직관적입니다.
• 문제의 해를 반드시 찾을 수 있다는 보장이 있습니다(해가 존재한다면).

 

단점: 

• 경우의 수가 매우 많을 때, 시간 복잡도가 매우 높아질 수 있습니다. 
• 효율성이 낮아, 큰 규모의 문제나 시간 제한이 엄격한 문제에는 적합하지 않을 수 있습니다.

 

예제:

 

Q) https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

 

 

 

A)

const solution = (sizes) => {
    //  내가 푼 코드
    let largest = 0;
    const arr = [];
    for (let i = 0; i < sizes.length; i++) {
        largest = largest < sizes[i][0] ? sizes[i][0] : largest < sizes[i][1] ? sizes[i][1] : largest;
        arr.push(Math.min(sizes[i][0], sizes[i][1]));
    }
    return largest * arr.reduce((acc, val) => acc > val ? acc : val, 0);

    //  참조한 코드
    // 각 명함을 [가로, 세로] 형태로 정규화하여 가로가 항상 세로보다 크거나 같도록 조정
    const normalizedSizes = sizes.map(([w, h]) => w >= h ? [w, h] : [h, w]);

    // 정규화된 명함 크기에서 가장 긴 가로와 세로 길이를 찾음
    const maxWidth = Math.max(...normalizedSizes.map(size => size[0]));
    const maxHeight = Math.max(...normalizedSizes.map(size => size[1]));

    // 가장 긴 가로와 세로 길이를 곱하여 지갑의 크기를 계산
    return maxWidth * maxHeight;
};