배열의 활용(투포인터)
연속된 자연수의 합
구상 개선
모든 경우의 수를 다 더해볼 때에,
- 1부터 시작:
1 + 2 + 3 + 4 + 5 = 15(어, 찾았다!) - 2부터 시작:
2 + 3 + 4 + 5 + 6 = 20(넘었네, 포기) - 3부터 시작:
3 + 4 + 5 + 6 = 18(넘었네, 포기)
이 과정을 손으로 쓰다 보면, 뭔가 엄청난 낭비가 발생하고 있다는 것을 눈치채게 됩니다.
1 + [2 + 3 + 4 + 5] [2 + 3 + 4 + 5] + 6
1에서 시작하는 합과 2에서 시작하는 합을 구할 때, 가운데 샌드위치처럼 끼어있는 [2 + 3 + 4 + 5]라는 구간을 컴퓨터가 두 번이나 계산하고 있다는 사실입니다.
파악
(최초 구상) 자연수 배열을 선언해서 여기에 더하는 숫자들만큼 순회하는 방법 worst한 경우
Naive한 경우 : 최악의 경우
int N;
cin >> N;
int cnt = 0;
for (int S = 1; S <= N ; S++){ // start_index
int sum = 0; // S가 초기화되면 Sum값도 초기화
for (int E = S; E <= N ; E++){ // end_index
sum = sum + E; // 구간합 = 연속된 값의 합, 15가 넘어가는 경우에 loop 중지
if (sum == N){
cnt ++;
break
}
if (sum > N){
break
}
}
}N = 15 이라 하자
S= 1, E = 5 일 때 cnt++
S= 2, 3일 때에는 E가 6까지 순회하며 N을 초과하여 break,
S = 4일 때에는 E가 6까지 순회하고, 이는 N과 같아 break
...
고로 1~6까지의 구간의 합을 생각해 보았을 때, S = 2, S = 3 일 때와 같은 경우에는 순회할 필요가 없다
따라서 불필요한 순회의 경우를 생략하려면,
투포인터 : 구간합이 N의 범위를 넘어가면, S를 차감해, 연속된 자연수의 합을 앞으로 전진 시킨다.
Naive 경우 개선
구간의 합을 구할 때에, 1~5, 2~5, 3~5 등의 구간을 반복적으로 순회 PrefixSum(구간합)에서 1,2를 빼는 동작으로 (2+3+4+5), (3+4+5), (4+5)의 연산에 필요한 순회를 줄일 수 있음
구상
연속된 자연수의 합에서, S E의 투포인터를 떠올린다, 투 포인터 사이에 있는 것이 연속된 구간이다.
이 투포인터에 E를 증가시키고 S를 감소시키는 방법으로 자연수의 공간에서 앞으로 전진시킨다.
구현
while (E < N){
// E가 N에 도달하면 탐색 종료 (어차피 E=N인 경우는 count=1로 셌으니까)
if (sum == N){
count++;
E++;
sum = sum + E;
}
else if(sum > N){
sum = sum - S;
S++;
}
else if(sum < N){
E++;
sum = sum + E;
}
}주몽의 명령
https://www.acmicpc.net/problem/2018
연속하지 않은 배열에서의 "값의 합" 구하기
파악
N는 원소의 갯수(배열의 길이), M은 숫자의 범위
정렬되지 않는 배열에서 A[S] + A[E] = M 을 만족하는 조합 찾기,
배열의 각 자리수에 일일이 대조하는 것은 의 시간복잡도.
배열을 정렬하면 투포인터 적용이 가능
배열의 시간복잡도는 이므로 이므로 배열 정렬에는 정도의 시간복잡도 이므로 가능하다
# include <cmath>
...
dobule N = 1.5e5;
dobule result = N * std::log2(number);구상 개선
배열을 A[N], 배열의 두 원소의 값의 합을 sum, 조건을 만족하는 갯수를count라 하자
두 원소의 포인터를 각각 S, E라 하자
초기구상
while (S <= E){
sum = A[S] + A[E];
if(sum == M){
count++;
if (E < N-1){
E++;
}
else if (E == N-1){
S++;
}
}
else if((sum < M) & (E < N-1)){
E++;
}
else if((sum < M) & (E == N-1)){
S++; // while문에 의해 S == N일 경우, 자동 종료됨
}
else if((sum > M) & (E == N-1)){
E--;
}
cout << S << " " << E << "\n";
}정렬된 배열 A[N]에서
1. S=0, E=1라 하고, A[S]+A[E]가 sum 보다 작으면 포인터 E를 증가시킨다. (반복)
2. E를 배열의 끝까지 더하였어도 A[S]+A[E]가 sum 보다 작으면 포인터 S를 증가시킨다. (반복)
3. A[S]+A[E]가 sum 보다 크면 포인터 E를 1 감소 시킨다.
초기구상의 문제점
- 포인터 E가 배열의 인덱스를 넘어가버려, 별도의 조건을 부여하여야 한다는 것이고,
- 또한 포인터 E를 감소 시킬 때에, 감소시키기 이전의 인덱스 값을 가지지 않게 하기 위해 E 값의 최대 제한도 감소시켜야 함(위 코드는 포인터가 진동하여 무한루프에 빠짐)
초기구상의 개선 : 한계선 max_E 도입
int S = 0;
int E = 1; // S와 같은 위치면 안 되므로 1에서 시작
int max_E = N - 1; // E가 오른쪽으로 갈 수 있는 최대 한계선
while (S < E) {
int sum = A[S] + A[E];
if (sum == M) {
count++;
S++;
E--;
max_E = E; // 짝을 찾고 E가 줄었으므로, 한계선도 당겨짐
}
else if (sum < M) {
if (E < max_E) {
E++; // 아직 한계선에 도달하지 않았다면 E를 계속 증가
} else {
// 한계선까지 갔는데도 합이 M보다 작다면?
// 현재의 S로는 절대 짝을 찾을 수 없으므로 S를 증가! (핑퐁 방지)
S++;
}
}
else if (sum > M) {
E--;
max_E = E; // 합이 커서 E를 줄였다면, 이제 그 이상은 볼 필요가 없으므로 한계선 갱신
}
}- 두 원소의 합이 sum일 때에는, S를 증가시키고 E를 감소시킨다.
- 이에 대한 반례로는 S가 동일하고 E를 감소하였을 때에도 sum이 나올 수 있는 경우이나, 이러한 경우는 없다
- 이 경우가 성립하려면 원소가 중복해서 있어야 하는데, 문제의 조건에 따라 이러한 경우는 성립하지 않음
개선
- 가 성립하지 않는다는 점(원소의 중복이 없다는 점)
- 위의 경우엔 E를 n-1 만큼 전진시킨 후에, 다시 감소시키며 이를 수식으로 나타내면 아래와 같음
S가 일 때에, E가 전진(증가)하는 경우는
S가 일 때 E가 후진(감소)하는 경우는
- (역순으로 내려가면 다시는 안올라가기 때문에 정확하게는 의 시간복잡도를 가지게 됨)
따라서, 처음부터 E의 이동방향을 --(감소)로 제한하면 E가 전진하는 경우를 사용하지 않아도 됨
구현
int S = 0;
int E = N-1;
int sum = 0;
int count = 0;
while (S < E){
sum = A[S] + A[E];
if(sum == M){
count++;
E--;
S++;
}
else if(sum < M){
S++;
}
else if(sum > M){
E--; // while문에 의해 S == N일 경우, 자동 종료됨
}
}좋은 수 구하기
https://www.acmicpc.net/problem/1253
N =A[S] + A[E]일 때 좋은 수이며 (단, )
초기파악
배열을 순회하면서 SUM값 마다 순회하며 투포인터로 두가지 조합을 찾자
- 배열 순회에 n, SUM값 마다 투포인터 순회하므로
- 시간복잡도는 n^2 인데 N=2,000() 이므로 시간제약 () 이내
수의 위치가 다르면, 값이 같아도 다른 수이다 배열의 원소 중복을 허용한다는 의미로 파악
숫자의 범위가 10^12 이므로, 4byte를 초과하여 배열 및 원소는 long형으로 선언
놓친 부분
수의 위치가 다르면, 값이 같아도 다른 수이다 배열의 원소 중복을 허용한다는 의미로 파악
와 문제의 조건 N = A[S] + A[E] 일 때 좋은 수이며 (단, )를 놓쳐,
다른 수 확인 로직을 빠뜨려 틀렸었음
구상
배열 입력 및 정렬(투포인터 전제 조건)
int N;
cin >> N;
vector<long> A(N,0);
// 배열 입력 받기
for (int i = 0; i < N; i++){
cin >> A[i];
}
// 배열 정렬하기
sort(A.begin(), A.end());find 값마다 투포인터 순회
- find 값 : 배열의 원소들 순회하며 할당 후 투포인터 순회
- 문제의 조건에 따라 find 값은 좋은 수의 조합에 포함되지 않아야 함
// 배열 순회하며 원소별 투포인터 순회
for (int i =0; i < N; i++){
long find;
find = A[i];
int S = 0; //start_index
int E = N-1; //end_index
// 투포인터 순회
// 0이 포함될 경우에, 자기자신의 인덱스와 0의 합으로 나타내어 지므로,
// N개의 수 중에서 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 그 수를 '좋다(GOOD)'고 한다.
while (S < E){
if((A[S]+A[E])==find){
// find와 다른 수인지 확인하는 로직 (다르다면 포인터를 옮겨야 함)
if (S != i && E != i){
S ++;
E --;
result ++;
break;
}
else if(S == i){
S++;
}
else if(E == i){
E--;
}
}
else if((A[S]+A[E]) > find){
E--;
}
else if((A[S]+A[E]) < find){
S++;
}
}
}