최솟값 만들기 (그리디 알고리즘)

https://school.programmers.co.kr/learn/courses/30/lessons/12941

프로그래머스

 

function solution(A,B){
    let answer=0;
    const sortedA=A.sort((a,b)=>a-b);
    const sortedB=B.sort((a,b)=>b-a);
    for(let i=0;i<A.length;i++){
        answer+=sortedA[i]*sortedB[i];
      
    }
    return answer
}

 

답은 매우 간단해 보이지만 왜 저렇게 정렬된 것끼리 곱한건지 생각해야한다, 곱한 값의 누적합을 최소로 만드는 문제이다. 이 문제를 풀기 위해 그리디 알고리즘을 쓴다. 그리디 알고리즘은 매 순간 당장 최선이라고 생각되는 선택을 해서 문제를 해결하는 방법이다.

 

그리디 알고리즘

그리디 알고리즘은 각 단계마다 가장 좋은 선택을 한다. 예를 들어, 우리가 어떤 선택을 할 때, 그 순간에 제일 좋아 보이는 (혹은 최소가 될 것 같은) 것을 고르는 것이다. 이 방법이 항상 전체 문제의 최적인 해를 보장하는 건 아니므로 상황에 따라 로직을 만들어야한다.

 

목표는 A와 B의 각 요소를 한 번씩만 사용해서, 각 쌍의 곱을 더한 값이 최소가 되게 하는 것이다.

 큰 수끼리 곱하면 결과가 커지기 때문에, A 배열에서 작은 수와 B 배열에서 큰 수를 곱해야 한다, 그래서 각각 오름차수, 내림차순으로 정렬한 뒤 곱한 것이다.

 

단순하게 이 순간에 당장 좋아보이는 것을 선택하면 되는것이다.

 

Lv.2 문제는 이게 처음으로 접하는 건데 처음이라 초심자의 행운이 깃들었나보다