😎 투 포인터 알고리즘
투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두개 의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.
- 흔히 2,3,4,5,6,7 번 학생을 지목해야 할 때 간단히
2번부터 7번까지의 학생이라고 부르곤 한다. - 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 데이터의 범위를 표현할 수 있다.
🎃 특정한 합을 가지는 부분 연속 수열 찾기
문제 설명
- N개의 자연수로 구성된 수열이 있다.
- 합이 M인 부분 연속 수열의 개수를 구하라
- 수행 시간 제한은 O(N)
😀 특정한 합을 가지는 부분 연속 수열 찾기 : 문제 해결 아이디어
투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있다.
1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 -> 카운트
3. 현재 부분 합이 M보다 작다면 -> end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 -> start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.
M = 5
[초기 단계] 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다
- 현재의 부분합은 1이므로 무시한다
- 현재 카운트: 0
[Step 1] 이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킨다
- 현재의 부분합은 3이므로 무시한다
- 현재 카운트: 0
[Step 2] 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다
- 현재의 부분합은 6이므로 무시한다
- 현재 카운트: 0
[Step 3] 이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킨다
- 현재의 부분합은 5이므로 카운트를 증가시킨다
- 현재 카운트: 1
[Step 4] 이전 단계에서의 부분합이 5이었기 때문에 start를 1 증가시킨다
- 현재의 부분합은 3이므로 무시한다
- 현재 카운트: 1
[Step 5] 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다
- 현재의 부분합은 5이므로 카운트를 증가시킨다
- 현재 카운트: 2
[Step 6] 이전 단계에서의 부분합이 5이었기 때문에 start를 1 증가시킨다
- 현재의 부분합은 2이므로 무시한다
- 현재 카운트: 2
[Step 7] 이전 단계에서의 부분합이 2였기 때문에 end를 1 증가시킨다
- 현재의 부분합은 7이므로 무시한다
- 현재 카운트: 2
[Step 8] 이전 단계에서의 부분합이 7이었기 때문에 start를 1 증가시킨다
- 현재의 부분합은 5이므로 카운트를 증가시킨다
- 현재 카운트: 3
특정한 합을 가지는 부분 연속 수열 찾기 코드:Java
import java.util.*;
public class Main {
public static int n = 5; // 데이터 개수
public static int m = 5; //찾고자 하는 부분합
public static int[] arr = {1,2,3,2,5}; // 전체 배열
public static void main(String[] args) {
int cnt = 0;
int intervalSum = 0; // 부분합
int end = 0; // 투 포인터에서 시작점은 순차적으로 for문을 통해 증가시키고 end만 자체적으로 증가시킴!
//start를 차례대로 증가시키며 반복
for (int start = 0; start < n; start++) {
//end를 가능한 만큼 이동시키기
while (intervalSum < m && end < n) { // 부분합이 m보다 작고 끝점이 마지막 인덱스 전이라면
intervalSum += arr[end];
end += 1;
}
//탈출하는 경우는 부분합이 m이상이거나 end가 끝까지 도달했거나 !
// 부분합이 m일 때 카운트 증가
if (intervalSum == m) {
cnt += 1;
}
intervalSum -= arr[start]; // 부분합이 m이든 m을 넘든 시작점 빼고 다시 시작해야지.
}
System.out.println(cnt);
}
}😀 구간합(Interval Sum)
🛴 구간 합 문제 : 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 수를 합한 값을 계산하는 문제
- 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정하자
- 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40 = 90이다
구간 합 빠르게 계산하기 : 문제 설명
- 𝑁개의 정수로 구성된 수열이 있다
- 𝑀개의 쿼리(Query)정보가 주어진다
- 각 쿼리는 𝐿𝑒𝑓𝑡와 𝑅𝑖𝑔ℎ𝑡으로 구성된다
- 각 쿼리에 대하여 [𝐿𝑒𝑓𝑡,𝑅𝑖𝑔ℎ𝑡] 구간에 포함된 데이터들의 합을 출력해야 한다
수행 시간 제한은 O(N + M) 이다.
구간 합 빠르게 계산하기 : 문제 해결 아이디어
접두사 합(Prefix Sum): 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것
접두사 합을 활용한 알고리즘은 다음과 같다
- 𝑁개의 수 위치 각각에 대하여 접두사 합을 계산하여 𝑃에 저장한다
- 매 𝑀개의 쿼리 정보를 확인할 때 구간 합은 𝑃[𝑅𝑖𝑔ℎ𝑡] - 𝑃[𝐿𝑒𝑓𝑡 - 1]이다
구간 합 빠르게 계산하기 : 코드(Java)
import java.util.*;
class Main {
public static int n = 5; // 데이터의 개수 N과 데이터 입력받기
public static int arr[] = {10, 20, 30, 40, 50};
public static int[] prefixSum = new int[6];
public static void main(String[] args) {
// 접두사 합(Prefix Sum) 배열 계산
int sumValue = 0;
for (int i = 0; i < n; i++) {
sumValue += arr[i];
prefixSum[i + 1] = sumValue;
}
// 구간 합 계산(세 번째 수부터 네 번째 수까지)
int left = 3;
int right = 4;
System.out.println(prefixSum[right] - prefixSum[left - 1]);
}
}