구간 합(Prefix Sum)
배열의 0번째 인덱스부터 특정 구간까지의 합을 새로운 배열로 정의하는 것. 선형 탐색 대신 구간 합 계산 방식으로 시간 복잡도를 줄임
특징
- 배열 A에 대해 합 배열 S를 정의
- 합 배열 S[i]는 배열 A의 0번째 원소부터 i번째 원소까지의 합에 대한 정보를 담음
⇒ S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] - 합 배열을 통해 선형 탐색을 할 필요가 없어지고 시간 복잡도가 O(1)로 줄어듦
구현 방식
- S[i] = S[i-1] + A[i]
특정 구간(i~j)의 구간 합 구하기
- S[j] - S[i-1]
Two Pointers 알고리즘
배열이나 리스트에서 두 개의 포인터(인덱스)를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용
특징
-
왼쪽 포인터 & 오른쪽 포인터를 사용. 이들은 각각 탐색 범위의 시작과 끝을 가리킴
-
왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하여 탐색하는 방식
-
두 개의 포인터를 적절히 이동시키며 시간 복잡도를 최적화할 수 있음
-
(1) 특정 배열 내에 target 값과 같거나 유사한 부분 합이 몇 개 존재하는지 계산
-
(2) 배열 내 target = arr[i] + arr[j]를 만족하는 (i, j) 쌍이 몇 개 존재하는지 계산
-
중첩 반복문의 시간 복잡도 : O(N²)
-
투 포인터의 시간 복잡도 : O(N)
실행 과정
조건)
- 두 포인터 start와 end는 0에서부터 시작
- 항상 start ≤ end를 만족
- start와 end가 배열의 크기(N)에 도달하면 알고리즘이 끝남
- start와 end 사이의 부분 합을 S라고 가정
- 부분 합이 M인 경우의 수를 cnt라고 가정
구현)
- S > M혹은 end == N : start++
- S < M : end++
- S == M : cnt++
Sliding Window 알고리즘
투 포인터 알고리즘과 유사. 배열이나 리스트에서 특정 길이의 특정 조건을 만족하는 구간을 효율적으로 탐색하는 알고리즘. 구간의 넓이가 일정하기 때문에 포인터가 2개일 필요가 없음
특징
-
핵심은 “중복된 데이터를 다시 계산하지 않고 재사용하는 것”
-
교집합의 정보는 공유하고, 양쪽 끝 원소만 갱신
-
(1) 고정 크기 구나 합의 최댓값/최솟값 찾기
-
(2) 문자열 패턴 탐색 : 아나그램 찾기
-
중첩 반복문의 시간 복잡도 : O(N²)
-
슬라이딩 윈도우의 시간 복잡도 : O(N)
실행 과정
조건)
- 배열의 구간 길이를 N이라고 가정
구현)
- 배열의 길이가 N인 첫 번째 구간의 부분 합 계산
- 첫번째 구간의 부분 합에서 맨 처음 배열 값을 빼고, 마지막 배열 값을 더함
Two Pointers 알고리즘과 Sliding Window 알고리즘의 핵심
시간 복잡도를 많이 차지하는 중첩 반복문이 아닌, start&end 포인터를 활용해 O(N)의 시간 복잡도 알고리즘을 구현하는 것
