3장 주요 개념 및 복습

3장의 주요 개념은 역시 Two Pointers Algorithm (이하 투 포인터 알고리즘) 이다. 대부분의 문제는 투 포인터 알고리즘을 적용하면 간단하게 풀 수 있는 문제이다. 

 

그 중에서 투 포인터 알고리즘의 변형 문제인 Sliding Window (이하 슬라이딩 윈도우) 를 익히면 완벽할 것 같다.

 

하지만 3-6. 최대 길이 연속 부분수열 문제를 다시 한번 확인할 필요가 있다. 

https://coding-review.tistory.com/275

3-6. 최대 길이 연속 부분수열

 

투 포인터 알고리즘에 대해서는 포스팅 한 내용이 있으니 해당 부분을 참고하면 될 것

https://coding-review.tistory.com/269

Two-Pointers-Algorithm

 

슬라이딩 윈도우에 대해서는 포스팅에 적혀있지 않으니 여기서 빠르게 정리한다. 

 

슬라이딩 윈도우는 투 포인터 알고리즘의 변형으로 투 포인터 알고리즘을 사용하지만
두 포인터 사이의 간격이 일정하다는 특징이 있다. 

배열의 크기가 size 이고 간격이 k 인 상황에서 연속적인 배열의 최댓값을 구하는 문제라고 가정

	private static int solution(int size, int k, int[] arr) {
        int answer = 0;
        int start = 0, end = k;
        int sum = 0;

        for (int i = 0; i < end; i++) {
            sum += arr[i];
        }

        while (end < size) {
            sum += arr[end];
            sum -= arr[start];
            end++;
            start++;
            
            answer = Math.max(answer, sum);
        }
        
        return answer;
    }
    
보통 슬라이딩 윈도우를 사용할때는 초기값을 정하고 그로부터 한칸씩 밀면서 진행하는 경우가
대부분이었다. 3-6 최대 길이 연속 부분수열 문제는 그런 형태는 아니었지만 대부분의 문제가 그러했다.