August 08, 2021
⚠️ 위 예시의 Two pointer 전략 설명
- 시작점은 첫번째 원소인 인덱스(0)을 가리키고 끝점은 마지막 원소인 인덱스(5)를 가리킨다.
- 현재 위치의 합이 Target(8)보다 크다면 끝점의 위치를 감소 시킨다.
- 현재 위치의 합이 Target(8)보다 작다면 시작점의 위치를 증가 시킨다.
- 현재의 위치의 합이 Target과 같다면 해당 위치를 저장하고 시작점과 끝점을 모두 증가 시킨다.
- 만약 시작점이 끝점보다 크다면 loop 종료 (
while left > right:
)
Two Pointer
와 달리 정렬되지 않은 배열에서도 사용 가능하다.⚠️ 위 예시의 Silding Window 전략 설명
k
는 주어진 구간이다. 주어진 구간 내 수를 합하여 최대 값을 찾는 문제이다.- 시작점(
i
)으로 부터k
까지 수들의 합을 구한다. → 1️⃣- 이후,
i
와k+i
한 범위의 수들의 합을 구한 뒤 1️⃣ 과 비교하여 최대값을 저장한다.- 이 과정을 반복하여 최대값을 구한다.