[C++ 백준 풀이] 1806번 : 부분합 / 2467번 : 용액 (두 포인터 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 '두 포인터 알고리즘'과 관련된 문제들인 1806번 : 부분합, 2467번 : 용액에 대한 풀이 코드와 해설을 다루고 있습니다.

 

두 포인터 알고리즘이란 1차원 배열 상에서 양 말단의 두 포인터 위치를 조작하며 원하는 값을 구하는 알고리즘을 의미하며, 구간을 구할 때 주로 사용됩니다.

 

구간의 양 끝단을 기준으로 매번 연산을 수행하려면 O(N^2)의 시간이 소요되기 때문에, 값을 미리 구해놓고 양 끝단 값만 조절해주면서 값을 변경하면 더 빠른 시간에 문제를 해결할 수 있습니다.

 

 

1806번 : 부분합

 

10000 이하의 자연스로 이루어진 N개 길이의 수열에 대해, 부분합이 S가 되는 것 중 가장 짧은 것의 길이를 구하는 문제입니다.

예를 들어 위의 예제 입력 1에서는 중간의 10+7이 15를 넘어가므로 가장 짧은 부분합의 길이는 2가 됩니다.

N의 범위가 10만 이하이기 때문에, 효율적인 알고리즘을 사용하지 않으면 시간 초과에 걸리게 되는 문제입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드의 원문은 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#define INF 100005
using namespace std;

int main() {
    int N, S, left = 0, right = 0, sum = 0, length = INF;
    int arr[100005] = {0, };
    scanf("%d %d", &N, &S);
    for(int i=0; i<N; i++) scanf("%d", &arr[i]);
    sum = arr[0];
    while(left <= right && right < N) {
        if(sum < S) sum += arr[++right];
        else if(sum == S) {
            if(right-left+1 < length) length = right-left+1;
            sum += arr[++right];
        }
        else if(sum > S) {
            if(right-left+1 < length) length = right-left+1;
            sum -= arr[left++];
        }
    }
    if(length == INF) printf("0");
    else printf("%d", length);
}

 

이러한 구간을 찾는 문제를 풀이할 때 유용한 알고리즘이 바로 두 포인터 알고리즘입니다.

두 포인터 알고리즘이란, 구간의 양 끝 점을 설정하고 while문의 조건에 따라 반복적으로 양 끝단의 포인터를 조정하면서 적절한 구간을 찾는 알고리즘입니다.

이 문제의 풀이 코드를 예시로 살펴보면, 우선 양 끝 점을 left, right라고 했을 때 초기의 left와 right의 주소를 모두 배열의 0번으로 설정합니다.

while문의 조건은 left가 right보다 커지거나 right가 오른쪽 끝 범위를 벗어나는 경우 끝나도록 설정합니다.

 

( i ) sum이 S 값보다 작다면, right 값을 증가시켜 sum이 증가되도록 합니다.

( ii ) sum이 S 값과 같다면, length가 최솟값인지 확인 후 맞으면 갱신하고, 역시 right 값을 증가시켜 sum이 증가되도록 합니다. (그래야 조건 ( iii )에서 left를 다시 증가시켜 sum을 감소 조정할 수 있음)

( iii ) sum이 S 값보다 크다면, left 값을 증가시켜 sum이 감소되도록 합니다.

 

위와 같이 두 포인터 알고리즘을 작성하면, left와 right가 적절히 증가하여 왼쪽 끝에서 오른쪽 끝까지 최소한의 탐색만 수행하여 탐색을 완료할 수 있습니다.

 

 

풀이 코드를 제출하여 채점을 해보면, 12ms라는 짧은 시간 안에 문제가 해결됨을 확인할 수 있습니다.

모든 경우의 수를 따져서 탐색을 했을 때 2000ms는 훌쩍 넘기는 것을 고려하면 알고리즘이 아주 효율적임을 알 수 있습니다.

추가로 시간을 더 단축시키기 위해서 cin, cout을 사용하지 않고 scanf와 printf를 사용하였으니 이 역시 참고해주시면 좋을 것 같습니다.

 

 

2467번 : 용액

 

이 문제도 역시 두 포인터 알고리즘을 사용하는 대표적인 문제 중 하나입니다.

문제를 보면, 오름차순으로 몇 개의 데이터가 주어졌을 때 두 데이터의 합이 0에 가장 가까운 두 데이터를 구하는 문제입니다.

단순히 합을 구하는 것이 아니라 두 데이터 자체를 출력해야 하므로 임시적으로 값을 저장하는 코드까지 필요할 것으로 보입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#define INF 2147483647
using namespace std;

int arr[100005] = {0, };
int abs(int a) { return a>=0?a:-a; }

int main() {
    int N, left, right, Min = INF, min_left, min_right;
    scanf("%d" ,&N);
    for(int i=0; i<N; i++) scanf("%d", &arr[i]);
    left = 0, right = N-1, min_left = 0, min_right = N-1;
    while(left < right) {
        if(abs(arr[left]+arr[right]) < Min) {
            Min = abs(arr[left]+arr[right]);
            min_left = left, min_right = right;
        }
        if(arr[left]+arr[right] == 0) break;
        else if(arr[left]+arr[right] > 0) right--;
        else if(arr[left]+arr[right] < 0) left++;
    }
    printf("%d %d", arr[min_left], arr[min_right]);
}

 

이 문제의 경우에는 위의 문제와 다르게, 시작점을 양 끝으로 잡아야 합니다.

왜냐하면 데이터들이 오름차순으로 배열되어 있고 데이터들의 음수 및 양수의 구분이 없으므로, 무조건 양 끝에서 탐색을 시작해야 최소한으로 탐색을 수행할 수 있게 됩니다.

(왼쪽 끝이나 오른쪽 끝에서 두 포인터가 시작하게 되면, 초기에 불필요한 탐색을 많이 수행하게 됨)

따라서 left를 0으로, right를 N-1로 설정하고 다음의 조건대로 탐색을 수행합니다.

 

( 공통 ) 두 데이터의 합의 절댓값이 Min보다 작은 경우 : 값을 갱신합니다.

( i ) 두 데이터의 합이 0인 경우 : 이보다 절댓값이 작을 수는 없으므로 반복문을 탈출하고 출력해줍니다.

( ii ) 두 데이터의 합이 0보다 큰 경우 : right을 1 감소시켜서 합을 감소하게 만들어줍니다.

( iii ) 두 데이터의 합이 0보다 작은 경우 : left를 1 증가시켜서 합을 증가하게 만들어줍니다.

 

 

풀이를 제출해보면 역시 20ms라는 짧은 시간 안에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

위의 문제와 동일하게 두 포인터 알고리즘을 사용하고, 시작점을 양 끝단으로만 잡아준다면 어렵지 않은 문제였습니다.