![]()
슬라이딩 윈도우 슬라이딩 윈도우란 일정한 길이를 이동시키면서 조건에 맞는 값을 찾는 알고리즘입니다. 배열에서 일정 범위의 합을 비교할 때 매우 유용한 방법으로, 값을 이동시킬 때 배열의 처음 값을 제거하고 배열의 마지막 값을 더해주기만 하면 되는데, 배열의 모든 값을 불러와서 더하는 연산을 피할 수 있어 매우 효율적입니다. 양 옆에 지점을 둔다는 점에서 투 포인터와 비슷한 점이 있지만, 투 포인터는 범위가 유동적으로 변하지만, 슬라이딩 윈도우는 범위가 고정되어 있다는 점이 차이점입니다. 다음은 투 포인터를 그림으로 표현한 예시입니다. 조건에 따라 범위가 유동적으로 변경되는 것을 볼 수 있습니다. 다음은 슬라이딩 윈도우를 그림으로 표현한 예시입니다. 범위는 항상 고정되어 있고, 배열은 좌우로만 이동합니다.
![]()
투 포인터 투 포인터란, 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터를 통해 O(N)으로 해결해주는 알고리즘입니다. 여기서의 포인터는 C언어에서의 포인터의 개념이 아니라, 해당 지점을 의미하기 위해 사용되는 개념입니다. 이중 for문으로 처리할 때 주로 i가 계산되고, 그 안에서 j가 계산되는데, j가 계산될 때 i에 대한 정보가 쓰이지 않습니다. 하지만 투 포인터 같은 경우에는 i에 대한 정보를 사용하여 포인터를 이동시킵니다. 투 포인터 문제는 이분 탐색으로도 풀 수 있는 경우가 많고, 그 반대의 경우 또한 많습니다. 투 포인터 문제는 크게 두 가지 유형이 있습니다. 정렬 후 양 옆에서 다가오는 것 left, right를 지정하고, 상황에 따라 left나 right가 ..
