[ Algorithm ] 투 포인터 (Two-Pointer) 알고리즘
투 포인터 알고리즘
1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다. 투 포인터 알고리즘을 통해 결과를 구하게 되면 시간복잡도를 O(n^2)에서 O(n)으로 단축시킬 수 있다.
포인터의 방향에 따라
투 포인터 알고리즘을 크게 2개로 나누면 두 포인터가 모두 같은 방향으로 움직이는 알고리즘과 두 포인터가 반대 방향으로 움직이는 알고리즘이 있다.
두 포인터가 같은 방향으로 움직이는 알고리즘
배열에서 두 개의 원소의 합이 s보다 큰 경우의 수를 출력하는 문제
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
int n, s;
int arr[MAX];
int cnt=MAX;
int sum=0;
int Min(int a, int b){
if(a>b)
return b;
else
return a;
}
void Input(){
cin>>n>>s;
for(int i=0; i<n; i++){
cin>>arr[i];
}
}
void Solution(){
int start=0;
int end=0;
while(start<=end){
if(sum>=s){
cnt=Min(cnt, end-start);
sum-=arr[start++];
}
else if(end==n)
break;
else
sum+=arr[end++];
}
if(cnt==MAX)
cout<<0<<endl;
else{
cout<<cnt<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
두 포인터가 다른 방향으로 움직이는 알고리즘
배열에서 두 개의 원소의 합이 0과 가장 가까운 수가 되는 경우를 찾는 문제
#include <iostream>
#include <algorithm>
#include <math.h>
#define MAX 100001
using namespace std;
int n;
int arr[MAX];
int min=INT_MAX;
void Input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>arr[i];
}
}
void Solution(){
sort(arr, arr+n);
int start=0;
int end=n-1;
int index1, index2;
while(start<end){
int sum=arr[start]+arr[end];
if(abs(sum)<min){
min=abs(sum);
index1=start;
index2=end;
}
if(sum<0){
start++;
}
else{
end--;
}
}
cout<<arr[index1]<<" "<<arr[index2]<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
Author And Source
이 문제에 관하여([ Algorithm ] 투 포인터 (Two-Pointer) 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/Algorithm-투-포인터-Two-Pointer-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)