알고리즘&자료구조 스터디 5주차 [Sliding Window, D&C]

May 4, 2023 🐰

🔑 일반적인 문제 해결 패턴을 습득하기 (Problem solving Patterns)

💪🏻 이 친구들은 알고리즘을 패턴화해 문제 해결에 도움을 줄 수 있는 착한 친구들이다!

벌써 네개했다! ✌🏻

🧠 frequency Counter
🧠 Multiple Pointers
🧠 Sliding Window
🧠 Divide and Conquer
🧠 Dynamic Programming
🧠 Greedy Algorithms
🧠 Backtracking
🧠 Many More!!!

🤯 오늘 배울 개념은 슬라이딩 윈도우와 분할과 정복이다.

🔑 SLIDING Window (슬라이딩 윈도우)

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

👩🏻‍🌾 An Example Sliding Window

MaxSubarraySum이라는 함수를 작성합니다. 
이 함수는 정수 배열과 n이라는 숫자를 받아들입니다. 
함수는 배열에서 n개의 연속된 요소의 최대 합계를 계산해야 합니다.

👩🏻‍🌾A naive solution O(N^2)

• 강의 코드와 비슷해서 내 코드로 작성

  function maxSubarraySum(array, n) {
  let max = 0;
  let result;
  //배열의 길이가 0 이면 null 값 리턴
  if (array.length === 0) return null;
  //반복의 마지막을 n개의 갯수만큼 제거후에 반복을 돌린다.
  for (let i = 0; i <= array.length - n; i++) {
    result = 0;
    //n 값의 크기만큼 순회시켜 배열의 결과값을 저장한다.
    for (let j = i; j < i + n; j++) {
      result += array[j];
    }
    //최댓값을 바꿔준다.
    if (result > max) max = result;
  }
  //최댓값 반환
  return max;
  }
  let result = maxSubarraySum([4, 2, 1, 6, 2], 4);
  console.log(result);

👩🏻‍🌾 Refactor Version O(N)

• Sliding Window를 사용한다. (이거 매우 신박한거 같다.)
  

1. 시작부터 num의 배열까지의 합을 maxSum에 저장한다.
2. tempSum에 maxSum을 저장
3. sliding window 알고리즘을 사용하여 for문 한개로 기존의 값의 앞부분을 빼고 뒷부분을 더한다.

function maxSubarraySum(arr, num) {

  let maxSum = 0;
  let tempSum = 0;
  // num 보다 작으면 null을 리턴
  if (arr.length < num) return null;
  // 기본 maxSum을 num까지의 값으로 저장한다. 
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  //tempSum에 전달 -> 나중에 나오는 반복문에 계속 저장될 예정
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    //sliding window.. 사용 기존 배열의 첫 값을 제거 + 그 후의 값을 저장
    tempSum = tempSum - arr[i - num] + arr[i];
    //최댓값.. 바꾸기!
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

👩🏻‍🌾 Coding Exercise7 : Sliding Window -maxSubarraySum

😼 Sliding Window -maxSubarraySum
정수 배열과 숫자가 주어지면 maxSubarraySum이라는 함수를 작성합니다. 
함수에 전달된 숫자의 길이로 하위 배열의 최대 합계를 찾습니다.

Time Complexity - O(n)
Space Complexity - O(1)

maxSubarraySum([100,200,300,400], 2) // 700
maxSubarraySum([1,4,2,10,23,3,1,0,20], 4)  // 39 
maxSubarraySum([-3,4,0,-2,6,-1], 2) // 5
maxSubarraySum([3,-2,7,-4,1,-1,4,-2,1],2) // 5
maxSubarraySum([2,3], 3) // null

👩🏻‍🌾 my solution

• 강의의 solution과 같게 sliding window 조지기.

function maxSubarraySum(array, n) {
  let maxSum = 0;
  let tempSum = 0;
  if (array.length < n) return null;
  for (let i = 0; i < n; i++) {
    maxSum += array[i];
  }
  tempSum = maxSum;
  for (let i = n; i < array.length; i++) {
    tempSum = tempSum - array[i - n] + array[i];
    maxSum = Math.max(tempSum, maxSum);
  }
  return maxSum;
}

👩🏻‍🌾 Coding Exercise8 : Sliding Window - minSubArrayLen

minSubArrayLen이라는 함수를 작성합니다. 
minSubArrayLen은 양의 정수 배열과 양의 정수 배열의 두 가지 매개 변수를 허용합니다.

이 함수는 합계가 함수에 전달된 정수보다 크거나 같은 연속 하위 배열의 최소 길이를 반환해야 합니다. 0이 없으면 0을 반환합니다.

Time: O(N)

Space: O(1)

minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

👩🏻‍🌾 my solution

• 2중 for문으로 해결했기에 보완이 필요하다.
• while을 통해 배열 내에 값을 비교한다.

function minSubArrayLen(array, result) {
  let n = 1;
  //length보다 작을때 비교 가능
  while (n < array.length) {
    let sum = 0;
// sum을 저장해놓는다.
    for (let i = 0; i < n; i++) {
      sum += array[i];
    }

    for (let i = n; i <= array.length; i++) {
      //sum이 클 경우 바로 return
      if (sum >= result) return n;
      else {
        sum = sum - array[i - n] + array[i];
      }
    }
    // 없을 경우 1개, 2개, 3개 씩으로 비교.
    n++;
  }
  return 0;
}

👩🏻‍🌾 my solution

function minSubArrayLen(nums, sum) {
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;

  while (start < nums.length) {
    // if current window doesn't add up to the given sum then 
        // move the window to right
    if(total < sum && end < nums.length){
      total += nums[end];
            end++;
    }
    // if current window adds up to at least the sum given then
        // we can shrink the window 
    else if(total >= sum){
      minLen = Math.min(minLen, end-start);
            total -= nums[start];
            start++;
    } 
    // current total less than required total but we reach the end, need this or else we'll be in an infinite loop 
    else {
      break;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

👩🏻‍🌾 Coding Exercise9 : Sliding Window - findLongestSubstring

findLongestSubstring이라는 함수를 작성합니다. 
이 함수는 문자열을 받아들이고 모든 고유한 문자가 
포함된 가장 긴 하위 문자열의 길이를 반환합니다.

findLongestSubstring('') // 0
findLongestSubstring('rithmschool') // 7
findLongestSubstring('thisisawesome') // 6
findLongestSubstring('thecatinthehat') // 7
findLongestSubstring('bbbbbb') // 1
findLongestSubstring('longestsubstring') // 8
findLongestSubstring('thisishowwedoit') // 6

👩🏻‍🌾 my solution

• 한국어가 부족해서 문제를 이해하는데 오래걸렸다.

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;

  for (let i = 0; i < str.length; i++) {
    let char = str[i];

    if (seen[char]) {
      start = Math.max(start, seen[char]);
      console.log(`start is ${char} , ${start}`);
    }
    longest = Math.max(longest, i - start + 1);
    console.log(`longest ${longest}`);
    seen[char] = i + 1;
    console.log(seen[char]);
  }
  return longest;
}

findLongestSubstring(""); // 0
let r = findLongestSubstring("rithmschool"); // 7

console.log(r);

🔑 Divide and Conquer (분할과 정복 패턴)

• 분할 정복은 앞으로 배울 트리, 정렬 등을 배우기전에 간단하게 배우는 것이다.
• 배열이나 문자열 같은 큰 규모의 데이터셋을 처리한다. (연결리스트나 트리가 될 수도 있다.)
• 배열이 왼쪽에서 오른쪽으로 가는 것을 조사하기보다는 배열을 작은 조각으로 세분하여 각 조각들을 어디로 이동시킬지 결정하는 작업을 하는 것이다.

정렬된 정수형 배열과 n을 매개변수로 받고, n이 위치한 인덱스를 리턴하는 함수 search를 작성합시다.
만약 값이 찾아 지지 않으면 -1을 리턴해주세요.

search([1,2,3,4,5,6],4); //3
search([1,2,3,4,5,6],6); //5
search([1,2,3,4,5,6],11); //-1

👩🏻‍🌾 A naive solution

• 선형 탐색 -> 우리가 아는 기본적인 왼쪽부터 오른쪽으로 찾기
• O(n)

  function search(arr, val){
    for(let i=0; i<arr.length; i++){
        if(arr[i] === val){
            return i;
        }
    }
    return -1;
  }

👩🏻‍🌾 Refactor

• binary Search ( 나중에 배울 이진트리..)
• log(n)
• function search(array, val){ let min = 0; let max = array.length -1; while(min <= max){ let middle = Math.floor((min+max)+2); let currentElement = array[middle]; if(array[middle] < val){ min = middle + 1; } else if(array[middle] > val){ max = middle -1; } else { return middle; } } return -1; }

분할과 정복 패턴에서 교훈은 그저 "더 큰 데이터셋을 취해 작은 하위셋으로 분할하고 다른 부분은 무시하는 방법을 알려주기 위함이였다."

🔑 review

• Sliding Window를 통해 지금까지 2중 for문을 통해 해결했던 문제들을 o(n)으로 바꿀수 있을거 같다.
• 예제가 조금 어려워서 골치 아팠지만... 앞으로 계속해서 반복 숙달하면 좋을거 같다.

💻 Source

• ✏️ Best JavaScript Data Structures & Algorithms Course by Udemy, last updated January 2022, accessed April 5, 2023 - https://www.udemy.com/
• ⌨️ reference gitHub - https://github.com/seunghyun0522/JavaScript-Algorizms-Data-Structure