[기본] 투 포인터

 

들어가며

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다. 알고리즘은 매우 간단합니다. 하지만 알고리즘에 익숙하지 않은 사람들은 투 포인터를 활용할 생각을 쉽게 하지 못합니다. 따라서 오늘은 투 포인터를 어떻게 사용하는지 알아봅시다.

 

투 포인터는 인접한 리스트에서 두 인덱스를 기록해가면서 조건 체크를 해 나갑니다. 여기서 중요한 것은 기록입니다. 포인터가 기록을 해나가기 때문에 전체 원소를 순회하면서 복잡도를 낭비하지 않아도 된다는 큰 장점이 있습니다. 투 포인터는 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.

 

문제1

백준 2018: 수들의 합 5(링크)

분석

주어진 제한시간은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있습니다. nlogn의 시간 복잡도 알고리즘을 사용해도 제한 시간을 초과하므로 O(n)의 알고리즘을 사용해야 합니다. 이럴 때 자주 사용하는 방법이 투 포인터입니다. 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 예정입니다.

 

풀이

#include <iostream>
using namespace std;

int main() 
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    
    int num;
    cin >> num;

    int start = 1, end = 1, sum = 1, result = 1;
    while (end != num)
    {
        if (sum == num)
        {
            end++;
            sum = sum + end;
            result++;
        }
        else if (sum < num)
        {
            end++;
            sum = sum + end;
        }
        else
        {
            sum = sum - start;
            start++;
        }
    }

    printf("%d\n", result);
    //cout << result;
}

 

투 포인터 이동 원칙

• sum > num: sum = sum - start_idx; start_idx++;  // 연속된 자연수에서 왼쪽 값 삭제(축소)
• - sum < num: end_idx++; sum = sum + end_idx;  // 연속된 자연수에서 오른쪽 값 추가(확장)
• - sum == num: end_idx++; sum = sum + end_idx; result++;  // 같은 경우 확장해서 다음 로직을 이어감

 

 

문제2

백준 1253: 좋은 수(링크)

 

 

 

분석

N의 개수가 최대 2,000이라 가정해도 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 합니다. O(nlogn)이 최적이겠네요. 정렬과 투 포인터를 활용해서 문제를 풀어볼 예정입니다. 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안됩니다. 이 점을 주의하면서 문제에 접근하겠습니다.

 

풀이

#pragma once
// 백준 1253: 좋은수
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main()
{
    long count;
    cin >> count;

    vector<long> data(count, 0);
    for (int i = 0; i < count; i++)
        cin >> data[i];


    std::sort(data.begin(), data.end());
    int start = 0;
    int end = 0;
    int result = 0;
    for (int i = 0; i < count; i++)
    {
        start = i == 0 ? 1 : 0;
        end = i == count - 1 ? count - 2 : count - 1;
        while (start < end)
        {
            if (start == i)
            {
                start++;
                continue;
            }

            if (end == i)
            {
                end--;
                continue;
            }

            if (data[start] + data[end] == data[i])
            {
                result++;
                break;
            }
            else if (data[start] + data[end] < data[i])
            {
                start++;
            }
            else
                end--;
        }
    }

    printf("%d\n", result);
}

 

투 포인터 이동원칙

• start_data + end_data > target: end--;
• start_data + end_data < target: start++;
• start_data + end_data == target: result++;

 

주의해야할 점

• 자기 자신을 좋은 수에 포함시키지 않기 위해 start, end가 i 와 같은 경우(투 포인터가 타겟과 같은 경우)는 먼저 제외처리했습니다.

 

 

정리

투 포인터는 보통 두 수의 합/곱 등, 연산을 통해 특정 값과 비교할 때 많이 사용됩니다. 투 포인터를 사용하지 않는 일반적인 생각은 이중 반복문을 사용해가면서 리스트의 두 값들을 연산하게 됩니다. 이미 여기서 부터 O(N^2)이 나와버리기 때문에, 이런 유형의 문제가 나온다면 주저하지말고 투 포인터를 떠올려야 합니다.