참고
투포인터 (Two Pointers)
NOTE
리스트에 순차적으로 접근해야 할 때 두 개의 점위치를 기록하면서 처리하는 알고리즘!
그림처럼 2개의 위치를 토대로 기록하며 처리
•
연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시킨다.
•
시간복잡도
◦
투 포인터 -> O(2n)
◦
완탐 → O(n^2)
예시 문제
NOTE
정렬된 정수 배열이 주어졌을 때, sum라는 함수를 작성하세요. 이 함수는 합이 0이 되는 첫 번째 쌍을 찾아야 합니다.
Input : findSumZero([-4, -3, -2, -1, 0, 1, 2, 3, 4])
Output : [-4, 4]
Input : findSumZero([-4, -3, -2, -1, 0, 1])
Output : [-1, 1]
Input : findSumZero([-4, -3, -2, -1, 0])
Output : null
Java
복사
예시 형식
무식하게 풀기
findSumZero(int[] arr) {
for(int i = 0; i < arr.length; i++) {
for(int j = i + 1; j < arr.length; j++) {
if(arr[i] + arr[j] == 0) {
return new int[]{arr[i], arr[j]}; // [arr[i], arr[j]
}
}
}
return null;
}
findSumZero([-4, -3, -2, -1, 0, 1, 2, 3, 4])
JavaScript
복사
하나의 숫자를 잡고, 배열의 모든 요소를 순회하는 방식
•
시간복잡도
•
공간복잡
Tow Pointer 접근법
findSumZero(int[] arr) {
int left = 0;
int right = arr.length - 1;
while(left < right) {
int sum = arr[left] + arr[right];
if (sum == 0) {
return new int[]{arr[left], arr[right]};
} else if (sum > 0) {
right--;
} else {
left++;
}
}
return null; // 합이 0이 되는 쌍을 찾지 못했을 때 null 반환
}
JavaScript
복사
우리는 배열이 정렬되어 있다는걸 잘 사용해야 한다!
•
시작과 끝점을 비교하면서, 0보다 큰경우와 작은경우를 나누어서 포인터를 이동한다.
•
시간복잡도
•
공간복잡도
참고 문제
슬라이딩 윈도우 (Sliding Window)
NOTE
연속된 데이터(주로 배열이나 리스트)에서 일정한 크기의 구간(윈도우)을 움직이며 문제를 해결하는 패턴
고정된 크기를 이동시킨다. (포인터 2개가 동일하게 움직임)
•
교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법
double sum = 0;
for(int i = 0; i < k; i++)
sum += nums[i];
double res = sum;
for(int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i-k]; // 오른쪽 값은 더하고, 왼쪽값은 뺀다
res = Math.max(res, sum);
}
return res / k;
Java
복사
윈도우 크기 ⇒ k
윈도우를 움직일때마다 오른쪽 값은 더하고 왼쪽값은 뺀다.
예시 문제
NOTE
정수 배열과 n이라는 숫자를 매개변수로 받습니다. 함수는 배열 내에서 연속적인 n개의 원소의 최대 합을 계산해야한다.
무식하게 풀기
maxSubarray(int[] arr, int n) {
if (num > arr.length) {
return null; // num이 주어진 배열의 길이보다 크면 null을 반환합니다.
// 연속된 num 개의 원소들의 합을 구할 수 없습니다.
}
/*
Java에서 사용할 수 있는 가장 작은 정수값이므로, 최대 합이 아무 작은 값이 되도 문제가 없습니다.
*/
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length - n + 1; i++) {
int temp = 0;
for (int j = 0; j < n; j++) {
temp += arr[i + j];
}
if (temp > max) {
max = temp;
}
}
return max;
}
JavaScript
복사
// 입력 : arr = [1, 3, 2, 4, 5, 1], n = 3
첫번째 반복문 : i = 0, j = 0, 1, 2
[1, 3, 2], 4, 5, 1 → 합: 6
두번째 반복문 : i = 1, j = 0, 1, 2
1, [3, 2, 4], 5, 1 → 합: 9
세번째 반복문 : i = 2, j = 0, 1, 2
1, 3, [2, 4, 5], 1 → 합: 11
세번째 반복문 : i = 2, j = 0, 1, 2
1, 3, [2, 4, 5], 1 → 합: 11
Java
복사
•
시간복잡도:
Slide Window 접근법
무식한 방법과 달리, 고정된 크기를 움직이므로 처음과 시작값에 대해서만 따로 처리해주는것
maxSubarray(int[] arr, int n) {
int maxSum = 0;
int tempSum = 0;
if (arr.length < n) return null;
for (int i = 0; i < n; i++) {
maxSum += arr[i];
}
tempSum = maxSum;
for (int i = n; i < arr.length; i++) {
tempSum = tempSum - arr[i - n] + arr[i];
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
JavaScript
복사
•
시간복잡도: