📖 문제 해결 패턴(Problem Solving Patterns)

다음은 알고리즘 문제를 패턴화해 문제 해결에 도움을 줄 수 있는 패턴들이다.

• Frequency Counter
• Multiple Pointers
• Sliding Window
• Divide and Conquer
• Dynamic Programming
• Greedy Algorithms
• Backtracking
  ...
  이 중 오늘 포스팅에서는 Sliding Window와 Divide and Conquer 패턴에 대해 이야기하겠다.

📌 기준점 간 이동 배열 패턴 : Sliding Window

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

여기서 window는 단일 변수, 하위 배열, 다른 문자열도 될 수 있다. 조건에 따라 창문이 이동하는데, 이때 시작 위치는 인덱스의 양끝, 중간 모두 가능하나 보통적으로는 인덱스의 시작에서 출발한다.

요런 느낌!

예시를 살펴보자.

정수형 배열과 정수 n을 매개변수로 하는 함수 maxSubarraySum를 작성한다. 이때 함수는, 배열에서 연속된 n개의 요소들의 합 중 가장 큰 값을 계산한다.

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

📌 Naive Solution

다음은 위 예시의 naive한 솔루션이다.

function maxSubarraySum(arr, num) {
	//num가 배열의 길이보다 크냐? -> 조건 일치시 null반환
 	if ( num > arr.length){
    	return null;
 	}
    //배열이 모두 음수로 구성되어 있으면 가장 큰 합은 어차피 음수이므로 -Infinity로
    //어떤 경우(특히 배열이 모두 음수인 경우)라도 max값이 요소의 합보다 작아지지 않도록 하기 위함
	var max = -Infinity;
    //어차피 시작인덱스는 arr.length-num까지이므로 for문의 조건식을 다음과 같이함
 	for (let i = 0; i < arr.length - num + 1; i ++){
    	temp = 0;
        //범위에 포함된 수들 더해줌
    	for (let j = 0; j < num; j++){
      		temp += arr[i + j];
    	}
        //max값 갈아치움
   		if (temp > max) {
      		max = temp;
    	}
  	}
	return max;
}

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

그렇지만 만약 배열이 엄청나게 커지는 경우에는, 반복문에서 max 값을 바꿔가면서 연산을 수행하는 것이 매우 비효율적이다.

📌 Refactored Solution

위를 리팩토링 하면 다음과 같이 풀 수 있다.

function maxSubarraySum(arr, num){
  	let maxSum = 0;
  	let tempSum = 0;
    //num가 배열의 길이보다 크냐? -> 조건 일치시 null반환
  	if (arr.length < num) return null;
    
    //for문 사용해서 num의 개수만큼 배열 합 더해줌(최대값의 초기화 과정)
  	for (let i = 0; i < num; i++) {
    	maxSum += arr[i];
  	}
    
    //tempSum을 일단 초기화
  	tempSum = maxSum;
    
    //위에서 num-1인덱스만큼 더해줬으므로 num부터 반복문 돌리기 
  	for (let i = num; i < arr.length; i++) {
    	//창문의 바로 이전값을 tempSum에서 빼준뒤 현재값을 더해준다고 생각하면 된다.
    	tempSum = tempSum - arr[i - num] + arr[i];
        //tempSum과 maxSum을 비교해서 큰값을 넣어준다.
    	maxSum = Math.max(maxSum, tempSum);
  	}
  return maxSum;
}

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

위 코드의 일부를 그려봤다. 두번째 for문의 첫번째 루프까지의 내용이다.

✏️ Sliding Window - maxSubarraySum

정수형 배열과 정수를 매개변수로 하는 maxSubarraySum함수를 작성한다. 이때 매개변수로 전달된 num으로 하위 배열의 최대 합을 찾는다. 하위배열은 원본 배열의 연속된 요소를 포함한다. 예를 들어, 첫번째 예시에서 [100,200,300]은 그 하위배열이지만, [100,300]은 그렇지 않다. 시간복잡도는 O(N)이고 공간복잡도는 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

function maxSubarraySum(arr, num){
    let tempSum = 0;
    let maxSum = 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;
    
}

위 코드와 일치한다.

✏️ Sliding Window - minSubArrayLen

앙의 정수 배열과 앙의 정수를 매개변수로 하는 minSubArrayLen을 작성한다. 이 함수는 원본 배열의 연속된 요소들을 값으로 갖는 하위배열의 요소 합이 매개변수로 받은 양의 정수보다 크거나 같을때 그 하위 배열의 최소 길이를 리턴한다. 만약 그런 값이 없으면 0을 반환한다. 시간복잡도는 O(N), 공간복잡도는 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

function minSubArrayLen(arr, num){
	//window 내부 요소의 합
    let windowSum = 0;
    //window 시작 인덱스
    let start = 0;
    //window 끝 인덱스
    let end = 0;
    
    //window 최소한 길이
    let minLength = 0;
    
    //start가 배열의 끝에 도달하지 않았을때
    while(start < arr.length){
    	//window요소의 합이 num보다 작고, window 끝 인덱스가 배열 길이보다 작을때(window가 아직 끝에 도달 x)
        if(windowSum < num && end < arr.length){
        	//window 끝 인덱스의 값 더해주고
            windowSum += arr[end];
            //window 늘리기
            end++;
            
        //window요소의 합이 num보다 크거나 같으면
        }else if(windowSum >= num){
        	//최소한의 길이가 0이라면 초깃값이므로 end-start뺀 값 할당
            //아니라면 minLength와 end-start중에서 작은 값 할당
            minLength = minLength === 0 ? end-start : Math.min(minLength,end-start);
            
            //window 내부 요소의 합에서 window의 첫번째 인덱스값 빼주고 start증가 => window 크기 줄임
            windowSum -= arr[start];
            start++;
        }else{
            break;
        }
    }
    
  	return minLength;
    
}

✏️ Sliding Window - findLongestSubstring

문자열을 매개변수로 갖는 함수 findLongestSubstring을 작성한다.

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

function findLongestSubstring(str){
  let dict = {};
  let longestLength = 0;
  let startIdx = 0;

  for (let endIdx = 0; endIdx < str.length; endIdx++) {
  	//문자열의 문자들 하나하나 char에 할당
    let char = str[endIdx];
    
    //만약 dict에 char이 있고, dict의 char의 값이 start인덱스보다 크거나 같으면 
    if (!isNaN(dict[char]) && dict[char]>=startIdx){
    	//start인덱스에 dict의 char키로 저장된 값에 +1해줌
        //현재 문자의 이전에 나타났던 위치 이후부터 시작하게 함
    	startIdx = dict[char] + 1;
    }
    //현재 반복문의 endIdx값과 startIdx의 차 & longestLength를 비교해서 큰 값을 넣음(만약 위에서 존재하는 값이었다면 longestLength보다 endIdx - startIdx + 1가 작았을 것이므로 값 바뀌지 않음)
    longestLength = Math.max(endIdx - startIdx + 1, longestLength);
    //dict[char]에 endIdx를 저장함(현재 반복문)
    //다음에 동일한 문자가 나타날 때, 그 문자가 이전에 나타났던 위치를 참조
    dict[char] = endIdx;
  }

  return longestLength;
    
}

💗 Sliding Window Solutions

💗 maxSubArray Solution

function maxSubarraySum(arr, num){
    if (arr.length < num) return null;
 
    let total = 0;
    for (let i=0; i<num; i++){
       total += arr[i];
    }
    let currentTotal = total;
    for (let i = num; i < arr.length; i++) {
       currentTotal += arr[i] - arr[i-num];
       total = Math.max(total, currentTotal);
    }
    return total;
}

위 내가 푼 풀이와 같다.

💗 minSubArrayLen 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){
    
    	//나랑 같은데 다른 부분
        //나는 Infinity로 초기화 안하고 0으로 해줘서 삼항연산자를 써줬음
      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;
}

💗 findLongestSubstring Solution

function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
 
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    //만약 있는 글자라면 start와 이전에 나타났던 인덱스를 비교해서 start에 저장함 -> 윈도우를 옮겨주는 느낌! 뒤에서 longest를 다시 저장해줘서 새로 윈도우를 위치시키는 느낌
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    //길이 비교함
    longest = Math.max(longest, i - start + 1);
    //현재 문자가 등장한 인덱스 저장하기 위해
    seen[char] = i + 1;
  }
  return longest;
}

📌 분할과 정복 패턴 : 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

📌 Naive Solution

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

O(N)의 시간 복잡도를 갖는다. 이 구조를 선형 탐색이라고 한다.

📌 Refactored Solution

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;
}

O(logn)의 시간 복잡도를 갖는다. 이 구조를 이진 탐색이라고 하고, 이것이 분할 정복 알고리즘이다.

이진 탐색 알고리즘은 간단하게 생각하면 색인이 없는 사전에서 단어를 찾는것과 비슷하다고 생각하면 이해하기 쉽다.

만약 색인이 없는 사전에서(정렬이 되어있는) heart를 찾으려고 한다면, 반을 나눠서 현재 페이지의 단어들이 h보다 앞인지 뒤인지를 알아내고, 만약 뒤에 있는 단어라면 뒤 쪽의 단어들은 버리고 앞쪽의 단어들에서 또 반을 나눠 앞의 과정을 반복할 것이다.

📘 참고 자료
https://www.udemy.com/course/best-javascript-data-structures/