투포인터 푸는 방법.
결론 240109
: 2번째 풀이인 양 끝점에서 모아지는 방법은 정렬시켜도 가능한 경우에
반드시 2번 풀이로 풀자!
-> 모아지는 방법의 경우, left 갈수록 작아지고, right 갈수록
커진다는 특징이 있음
- endP는 이미 최대값고, startP는 이미 최소값임을 인지해야 함.
언제, 왜 사용할까?
- 연속된 원소 간의 계산을 할때 떠올라야 함!
2, 반드시 연속된 원소가 아닌 경우에도,
두 인덱스 간의 연산을 할 때 사용함.
-> 시간 복잡도는 O(N) 임.
: 연속된 인덱스의 원소 끼리 더한다고 했을때
시간 복잡도는 n * n 의 비용이 발생한다는 것을 생각할 수있음.
start ~ end (인덱스 5개 확인 이라면)
-> 다음 시작값은 에는 v[start++] 해서 또 진행 하겠지??
but 투포인터를 사용하면, 5개 원소 계산 완료 된 후, start 원소만 제거 한 후, end + 1 원소만 더하면 되므로,
시간 복잡도는 훨씬 절약 됨을 알 수 있음!
또는 end 쪽에서 원소를 발견할 경우, end를 제외하면 됨.
🤑원리
- 연속된 원소들간의 합을 구한다고 할 때, 합이 커진다는 것을
정렬에 구분없이 원소들의 갯수가 많다는 것을 의미함.
물론, 갯수가 적어도 원소의 값이 커서, 합이 상대적으로 클수는
있지만, 상식적으로 생각하면, 원소의 갯수 많을 수록 합이 커짐
😊푸는 방법.
- 1번과 2번 중에 어떤 것을 선택해서 풀것인가에 대해서
1.언제 start에서 같이 출발?
2.양끝점에서 모아지는 방식으로 진행?
1) 컨테이너들의 위치를 변경해도 될 경우, 정렬해서 2번 풀이로 하자.
2번 풀이의 경우에는 오름 차순이므로, 한번 처리가 된 원소에 대해
걱정할 필요가 없음.
1 2 3 4 5 6 이렇게 원소가 있을 경우,
: 왜냐하면 해당 2개의 인덱스에서 값을 구했다고 한다면, left쪽은 왼쪽으로 갈수록
값이 작아지는 특성이 있고, right는 오른쪽으로 가는 특성이 있다는 성질을 이해야 함.
- 참고 : 큰돌님 블로그
https://blog.naver.com/jhc9639/222319124359 - 1번으로 풀 경우에 반례 : https://velog.io/@kwt0124/3273%EB%B2%88.-%EB%91%90-%EC%88%98%EC%9D%98-%ED%95%A9
2) 정렬 시키면 안되고, 컨테이너 위치를 고수할 경우, 1번으로 풀자.
1번
첫 인덱스부터 start, end 값 서로 시작해 마지막 인덱스까지 달려 나가기
- left를 for문으로 돌리고 , while문으로 right를 증가하는데, right의
조건이 필요하다. right < size() 까지만 진행하도록- 관련 문제 : 수들의 합2.
이 문제에서 end값을 뒤에서 부터 앞으로 이동시키면, for문으로 sum을 구해야 하므로, 시간 복잡도가 커짐. 차라리 end를 앞에서부터 뒤로 진행하는 것이
훨씬 효율적임.
2번
유일한 원소들 가운데서, 정렬된 상태에서,
가장 작은 원소를 시작으로, 가장 큰 원소를 끝점으로 해서
최적의 해를 구할때까지 2개의 포인터를 가운데로 위치시키는
알고리즘!
- 관련 문제 : , 주몽.
😊2번째 투포인터에 대해서
언제 start 인덱스를 ++할것인가?
언제 end인덱스를 --할 것인가?
아니면 start, end 인덱스 2개를 증감시킬 것인가?
예시
1 2 3 4 5 7 9 10 12 14 15
타겟팅값 : 13
가) 1과 15 -> 16 vs 13 안되므로. 타겟값보다 크므로,
16보다 값을 줄여야 함.
-> end인덱스를 줄이자.
나) 진행 중에 1 과 12 -> 13 vs 13 발견 카운팅
start와 end를 증감하자.
다) 2와 10 -> 12 vs 13 안되므로, 타겟값보다 작으므로,
12보다 값을 커지게 해야 함.
-> start 인덱스를 증가해서 올리자!
반복문 조건
: 등호를 포함 하면 안됨.
왜냐하면? 등호를 포함하게 되면, 동인한 원소값으로 계산을 하기 때문임
유일한 원소들로 계산을 진행 중인 알고리즘!
-
0번. 정렬을 무조건적으로 해야 가능한 알고리즘!
-
0번. 원소가 유일해야 함. 중복된다고 하면 불가능함!
-
1번. 리스트에 순차적, 연속적으로 접근해야 할때 두개의 점을 이용해 위치를 기록하면서 처리하는 방법. 중간에 하나라도 제외되면 안된다.
추가
: 두 개의 정점을 통해 사이의 값을 처리한다거나, 두 개의 정점을 처리할 경우,
시간복잡도가 크다고 생각하면, 투포인터를 사용하자. -
2번. 시작 값과 마지막 원소를 기준으로 해서 원하는 결과 값이 나올 경우,
시작값을 ++ 증가시키면서 처리함. (단, 조건은 중복된 원소가 없을 경우,)
: 관련 예제 : 백준 3273번, 두 수의 합. -
참고
https://www.youtube.com/watch?v=rI8NRQsAS_s&list=PLRx0vPvlEmdAZ6xXAUyBbLQa2-Ideakb-
해당 벡터에서 연속된 수열 중에서 합이 5인 경우의 수는?
- 나동빈님의 코드 -> 이걸로 진행하자.
using namespace std;
int n = 5; // 데이터의 개수 N
int m = 5; // 찾고자 하는 부분합 M
int arr[] = {1, 2, 3, 2, 5}; // 전체 수열
int main() {
int cnt = 0;
int intervalSum = 0;
int end = 0;
// start를 차례대로 증가시키며 반복
for (int start = 0; start < n; start++) {
// end를 가능한 만큼 이동시키기
while (intervalSum < m && end < n) {
intervalSum += arr[end];
end += 1;
}
// 부분합이 m일 때 카운트 증가
if (intervalSum == m) {
cnt += 1;
}
intervalSum -= arr[start];
}
cout << cnt << '\n';
}- 내 코드
#include <iostream>
#include <vector>
using namespace std;
//5를 만들수 있는 연속 수열 만들기
int main()
{
//1,2,2는 포함되지 않는다. 연속되지 않으므로.
vector<int>v = { 1,2,3,2,5 };
int target = 5;
int left = 0;
int right = 0;
int sum = v[right];
int answer = 0;
while (right < 5 && left <= right)
{
if (sum < target)
{
right++;
if (right >= 5)
break;
sum += v[right];
}
else if (sum == target)
{
answer++;
right++;
if (right >= 5)
break;
sum += v[right];
}
else
{
sum -= v[left];
left++;
}
}
cout << answer << endl;
}
코드로 구현할때
- 인덱스를 나타내는 두개의 변수와
- 사이의 값들을 더해야 하므로, 인덱스가 같으면 가산 하면 안된다.
관련문제
https://www.acmicpc.net/workbook/view/3264
연습_1.브루트포스 파일 참고하자.
3문제 있음.
수들의 합2, 부분합, 소수의 연속합.
수들의 합
-> 문제 유발 코드이다.
백준에서는 통과가 되지만, sum += v[right] 부분에서
인덱스 초과할 경우 문제된다.
변경하자...
저장값을 1 더 늘리자.
부분합
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int>v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
int left = 0;
int right = 0;
int sum = 0;
int min = INT_MAX;
for (int left = 0; left < n; left++)
{
while (right < n && sum < m)
{
sum += v[right];
right += 1;
}
if (sum == m)
{
int temp = right - left;
if (temp < min)
min = temp;
}
sum -= v[left];
}
if (min == INT_MAX)
min = 0;
cout << min ;
}