최솟값 만들기

문제의 조건 및 분석

1. 배열의 길이가 짧을때는 모든 가짓수를 실행할 수 있겠지만 배열의 크기가 1000씩이나 되면 $1000^2 = 10^6$이 되므로 매우 비효율적일 것이다

2. 두 배열을 정렬하고 짧은 배열의 길이만큼 자르고, A는 정순, B는 역순으로 곱하는게 가장 합리적일것같다.

나의 풀이

function sol00(A, B) {
  let length = 0;
  let answer = 0;

  if (A.length >= B.length) {
    length = A.length;
  } else {
    length = B.length;
  }

  A.sort((a, b) => a - b);
  B.sort((a, b) => b - a);

  for (i = 0; i < length; i++) {
    answer += A[i] * B[i];
  }

  return answer;
}

어렵지 않은 문제여서 나의 생각을 그대로 코드로 구현하는게 가능했다

다른 사람의 풀이

function solution(A,B){
    A.sort((a, b) => a - b)
    B.sort((a, b) => b - a)
    return A.reduce((total, val, idx) => total + val * B[idx], 0)
}

이 사람 뿐 아니라 다른 사람들의 풀이를 봐도 A와 B의 길이가 다르다는 가정하에 풀이는 없다...
난 문제의 조건을 1<= 배열A의 크기 <= 1000 && 1<= 배열B의 크기 <= 1000로 이해했는데 실제로는 1<= 배열A의 크기 = 배열B의 크기 <= 1000였던듯하다

속도 비교

시간복잡도

두 함수 모두 배열을 sort하기 때문에 $O(n \log n)$의 시간복잡도를 가진다.

배열 원소의 크기를 증가

원소의 크기를 변경시키는 것은 성능에 영향을 미치지 못했다

배열의 길이를 증가

$100 \log 100 = 664$
$1000 \log 1000 = 9970$ => 15배
$10000 \log 10000 = 132900$ => 200배

배열의 길이를 100으로 고정하고, 대신 길이를 10배, 100배로 만들어서 시간을 측정했다.

10배 증가할때 예측과 너무 다른 값이 나온다. GPT의 답변으로는 배열의 크기가 커서 캐시미스와 오버헤드가 발생한것 같다고한다. 100배로 갈때는 어떤 특이점을 넘어서 그 차이가 크게 나지 않는 것이라고도한다

과연 그 말이 사실일까 궁금해서 배열의 길이를 조절해봤다

기본 배열의 길이를 짧게 (100 > 7)

**기본 배열의 길이를 길게 (100 > 200)

확실히 배열의 길이를 짧게 만들면 오차가 줄어들었고, 반대로 배열의 길이를 길게 만들면 큰 변화가 없다.

배운점

1. for문 보다는 reduce문이 살짝이지만 더 빠르다

2. 배열등의 길이가 너무 길어지면 성능저하가 일어날 수 있다.
   하지만 그 크기가 일정 수준을 넘어서면 그 차이가 체감이 잘 돼지 않는다