[알고리즘] 문제 해결 패턴 (3) 기준점 간 이동 배열 패턴

기준점 간 이동 배열 패턴

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. 

sliding window 접근법

창문을 하나 만들어야 한다. 창문은 단일변수, 하위배열, 또는 필요한 경우 다른 문자열도 될 수 있다. 조건에 따라 창문을 이동시키며, 시작 위치에서 시작하면 보통 왼쪽에서 오른쪽으로 이동한다. 오른쪽에서 왼쪽으로 이동도 가능하고 가운데 위치에서 시작할 수 있다. 그러나 보통 창문을 왼쪽, 즉 요소의 시작 위치 또는 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동한다. 

 

규모가 큰 데이터셋에서 데이터의 하위 집합을 추척하는 문제에 유용하다.

예시 문제

정수의 배열과 n이라는 수를 받아들이는 maxSubarraySum이라는 함수를 작성해라. 이 함수는 배열에서 n개의 연속적인 요소의 최대 합을 계산해야한다. (배열에는 정수만 있으면 된다. 두 번재 숫자를 전달하는 함수는 해당 배열의 연속된 요소의 가장 큰 합계를 계산하면 된다. 2(개)를 전달하면 1이 반환되어야 한다. 8과 2는 연속된 두 숫자 중에서 합계가 가장 크기때문이다. )  

maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null

접근 방법

// 매개변수는 배열과 숫자를 취한다. num은 구하고자하는숫자의 개수이다.
function maxSubarraySum(arr, num) {
  // 각각의 경우에 숫자가 배열의 길이보다 큰지 확인
  // 연속된 세개의 정수의 가장 큰 합을 구해서 정수가 두개만 있거나 비어있으면 null이 반환
  if (num > arr.length) {
    return null;
  }

  // 양수로만 작업을 하지 않는 한 0에서 시작한 것은 전혀 도움이 안되기에 -Infinity로 설정
  let max = -Infinity;

  // for문은 배열의 끝이나 거의 끝까지 도달한다.
  for (let i = 0; i < arr.length - num + 1; i++) {
    // temp에는 각 루프의 합계가 저장된다.
    let temp = 0;

    for (let j = 0; j < num; j++) {
      // j의 위치(index)가 옆으로 한 자리 이동하는데, 세가지 숫자를 더하는 방법이라고 볼 수 있다.
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

 

-Infinity란?

자바스크립트에서 사용되는 특별한 값, 음의 무한대를 나타낸다.

숫자형 데이터의 일부이며, 어떤 숫자보다도 항상 작다. 

이 값은 일반적으로 초기값으로 사용되며, 특정 조건에서 최대값을 찾는 알고리즘으로 유용하다.

console.log(-Infinity < -100); // true
console.log(-Infinity < 0);    // true
console.log(-Infinity < 100);  // true

 

한마디로 아직 최대값이 설정되지 않았다라는 의미이다. 

 

시간 복잡도 O(n²)이다. 

 

이 해결책의 안좋은점은 

세가지 항목으로 진행하려면서 합계를 구할때 20개 넘개의 연속된 숫자들 중에서 가장 큰 합계를 찾을 경우에는 비효율적인 방식이다. 

아주 큰 배열이있으면 빅오 표기법을 사용해 무하능로 연장할 수 있음을 기억해야된다. => 비효율적이라는 뜻

 

🤔 arr.length-num+1의 의미 <- 슬라이딩 윈도우가 시작할 수 있는 최대 인덱스 위치를 계산해준다.

arr.legnth: 배열의 총 요소 개수

num: 한 번에 더할 연속된 숫자의 개수

arr.legnth-num:윈도우가 배열 끝까지 갈 수 있는 "시작 위치"의 최대값

+1: 시작 인덱스가 0부터 시작하니까, 가능한 모든 시작 위치의 개수를 포함해 더해준다. 

 

=> arr.length - num은 "마지막 윈도우의 시작 인덱스"이고, +1은 "총 반복 횟수"를 맞추기 위한 조정이다. 

배열 끝까지 num개를 딱 맞춰서 계산하려면, 시작점이 너무 뒤로 가면 안 된다. 그래서 arr.length - num으로 범위를 좁히고, +1로 가능한 모든 경우를 포함해야된다.

 

리펙토링 

아래의 코드 방법은 슬라이딩 윈도우 방법이다. 

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  // 예외처리
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3);

 

시간 복잡도는 O(n)이므로 루프에서 한번만 빼서 값을 구할 수 있는 장점이다. 

 

tempSum = tempSum - arr[i - num] + arr[i];

arr[i - num]: 이전 윈도우의 맨 앞 요소를 제거
arr[i]: 새로운 요소를 추가
이렇게 해서 다음 윈도우의 합을 빠르게 구함

 

🤔 for (let i = 0; i < num; i++) { maxSum += arr[i]; } 이 부분이 이해가 잘 안간다.

maxSubarraySum([100,200,300,400], 2) // 700 이걸 적용할 경우 100이랑 200밖에 순회를 못하는거 아닌가?에 대한 궁금증이 생겼다.

for (let i = 0; i < num; i++) {
  maxSum += arr[i];
}

 

이 코드는 배열에서 처음으로 나올 수 있는 연속된 num개의 요소의 합을 미리 구하는 식이다. 

maxSubarraySum([100, 200, 300, 400], 2) // 700

이 코드는 2개의 숫자의 합 중 최대값을 구하는것

 

핵심을 이해하지 못했다. 

---------------------------------------------------------------------------------------------------------------------------

정리를 해보자면 

for문이 총 2개가 나온다. 

 

1. 첫번째 for문, 첫번째 윈도우를 계산한다.

 for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }

maxSumbarraySum ([100,200,300,400], 2) 

i = 0 → 100

i = 1 → 200

 

i = 0일경우 i < 2; ...

maxSum + 100 

maxSum = 100이다.

 

i = 1일경우 i < 2; ...

maxSum(100) + 200

maxSum = 300이다. 

 

여기서 첫번째 num = 2임으로 첫번째 for문은 중단된다. 

 

여기서 새롭게 알게된 점..! 💡

두번째 for문에서는 i = 0 부터 계산하지 않아도 된다.

이미 첫번째 for문에서 계산했기 때문이다!!

 

2. 두번째 for문, 두번째 윈도우를 계산한다. 

  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }

 

i = 2일때부터 계산하면 된다.

i = 2; i < 4; i++

tempSum의 값흔 현재 300이다.

tempSum = 300 - arr[2-2] + arr[2];

========= 300 - arr[0] + arr[2];

========= 300 - 100 + 300

========= 500 

이제 tempSum = 500이다.

300이랑 500중 500이 더 큼으로 maxSum = 500

 

i = 3일 경우 

i = 3; i < 4; i++

tempSum = 500이다.

tempSum = 500 - arr[3-2]+arr[3];

========= 500 - arr[1] + 400

========= 500 - 200 + 400

========= 700

500이랑 700 중 700이 더 크다.

그래서 maxSum = 700

 

⭐🧠

tempSum = tempSum - arr[빠지는 인덱스] + arr[새로 들어오는 인덱스]

앞에서 하나 빼고 뒤에서 하나 더해