[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안
목차
반응형
해당 글에서는 투 포인터 알고리즘에 대해 이해를 돕기 위해 작성한 글입니다.
1) 투 포인터 (Two Pointer Algorithm)
💡 투 포인터 (Two Pointer Algorithm)
- 배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘입니다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용됩니다.
- 투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. - 또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가집니다. - 해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있습니다.
1. 투 포인터 수행 단계
💡 투 포인터 수행 단계
1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정합니다.
2. 두 포인터 사이의 구간을 조사하고 조건을 확인합니다.
3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료합니다.
4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킵니다.
5. 다시 2번 단계로 돌아가 반복합니다.
2. 투 포인터 시간 복잡도
💡 투 포인터 시간 복잡도
- 투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적입니다. 또한 한 번의 반복으로 모든 요소를 처리하기에 효율적입니다.
- 일반적으로 빅오 표기법을 이용하여 표기하였을때 O(N)입니다. 이는 배열이나 리스트 크기에 비례하여 알고리즘의 수행시간이 증가한다는 의미입니다.
https://adjh54.tistory.com/186
2) 투 포인터 (Two Pointer Algorithm) 종류
1. 고정 길이 슬라이딩 윈도우
💡 고정 길이 슬라이딩 윈도우
- 고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색합니다.
- 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행합니다. - 이 유형은 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용될 수 있습니다.
- 윈도우의 크기를 필요에 따라 변경하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행합니다. - 이 유형은 최소 길이 부분 배열이나 최대 길이 부분 배열을 찾는 등의 문제에 사용될 수 있습니다.
3. 두 포인터의 합과 차
💡 두 포인터의 합과 차 - 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결합니다.
- 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있습니다.
https://colabear754.tistory.com/69
3) 투 포인터 알고리즘을 활용방안
💡 투 포인터 알고리즘을 활용방안
- 투 포인터 알고리즘을 통해 간단한 예시를 통해 활용방법에 대해 알아봅니다.
1. 투 포인터 합 (Two Pointer Sum)
💡 투 포인터 합 (Two Sum Sum)
- 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값을 갖는지 확인하는 문제입니다. - 투 포인터 알고리즘을 사용하면 선형 시간에 문제를 해결할 수 있습니다.
💡 간단한 예시
- 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제를 해결합니다.
1. left와 right라는 두 개의 포인터를 배열의 양 끝에서 시작합니다.
2. left 값보다 right 값이 큰 경우일 때까지 반복합니다.
3. left와 right의 합을 sum에 저장합니다.
4.1. 만약 sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동하며 right 인덱스는 왼쪽으로 이동합니다.
4.2. 그렇지 않고 sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동시킵니다.
4.3. sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동시킵니다.
6. 해당 조건에 만족하는 count 값을 반환합니다.
/**
* 01. 투 포인터 합 문제 (Two Sum Problem)
* 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제를 해결합니다.
*
* @return ResponseEntity<ApiResponse>
* @link
* @since 2024.01.
*/
@GetMapping("/1")
public ResponseEntity<Object> question01() {
int[] nums = {1, 2, 3, 4, 5, 6, 7};
int target = 12;
int count = 0;
// 1. left와 right라는 두 개의 포인터를 배열의 양 끝에서 시작합니다.
int left = 0;
int right = nums.length - 1;
// 2. left 값보다 right 값이 큰 경우일때까지 반복합니다.
while (left < right) {
// 3. left와 right의 합을 sum에 저장합니다.
int sum = nums[left] + nums[right];
// 4.1. sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동하며 right 인덱스는 왼쪽으로 이동합니다.
if (sum == target) {
count++;
left++;
right--;
}
// 4.2. sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동시킵니다.
else if (sum < target) {
left++;
}
// 4.3. sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동시킵니다.
else {
right--;
}
}
// 5. 해당 조건에 만족하는 count 값을 반환합니다.
return new ResponseEntity<>(count, HttpStatus.OK);
}
💡 이미지로 이해하기
- 해당 조건에 만족할 때까지 left는 오른쪽으로 이동하고 합을 찾습니다. 최종 값을 찾으면 count ++를 해줍니다.
2. 투 포인터 슬라이딩 윈도우 (Sliding Window with Two Pointers)
💡 투 포인터 슬라이딩 윈도우 (Sliding Window with Two Pointers)
- 고정된 길이의 윈도우를 배열이나 리스트에서 슬라이딩하면서 특정 조건을 만족하는 부분 구간을 찾는 문제에 사용됩니다. - 예를 들어, 최대 연속 부분 배열의 합을 구하는 등의 문제에 적용할 수 있습니다.
💡 간단 예시 - 슬라이딩 윈도우를 이용하여 배열에서 k의 길이만큼의 합 중 최대 값을 찾는 예시입니다.
/**
* 3. 투 포인터 정렬 (Two Pointers for Sorting)
* 투 포인터를 사용하여 정렬된 두 배열을 한 번에 비교하고, 작은 값을 새로운 배열에 추가하는 방식으로 문제를 해결할 수 있습니다.
*
* @return ResponseEntity<ApiResponse>
* @link
* @since 2024.01.
*/
@GetMapping("/3")
public ResponseEntity<Object> question03() {
int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] nums2 = {10, 11, 18, 13, 14, 15};
// 1. merged라는 num1 배열과 num2 배열을 합친 새로운 배열을 구성합니다.
int[] merged = new int[nums1.length + nums2.length];
int i = 0;
int j = 0;
int k = 0;
// 2. i와 j 포인터를 사용하여 nums1과 nums2 배열을 하나씩 비교하여 i, j가 더 작은 경우 해당 반복문이 종료됩니다.
while (i < nums1.length && j < nums2.length) {
// 3.1. num2 배열의 값이 큰 경우 : merged 배열에 num1 값을 넣고 i를 증가합니다.
if (nums1[i] < nums2[j]) {
merged[k] = nums1[i];
i++;
}
// 3.2 num1 배열의 값이 큰 경우 : merged 배열에 num2 값을 넣고 j를 증가합니다.
else {
merged[k] = nums2[j];
j++;
}
// 4. 한번의 루프가 종료될때 k 값을 증가합니다.
k++;
}
// 5. i가 num1의 길이보다 작으면 num1의 나머지 요소들은 merged에 할당하고 i와 k를 증가시킵니다.
while (i < nums1.length) {
merged[k] = nums1[i];
i++;
k++;
}
// 6. j가 num2의 길이보다 작으면 num2의 나머지 요소들은 merged에 할당하고 j와 k를 증가시킵니다.
while (j < nums2.length) {
merged[k] = nums2[j];
j++;
k++;
}
return new ResponseEntity<>(merged, HttpStatus.OK);
}
