알고리즘 - 투포인터

이번 글에서는 알고리즘의 투포인터에 대해 알아보겠습니다

투포인터란 배열에서 원래는 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘

2개의 포인터가 배열을 돌때 각 포인터가 모든 배열을 1번 돌때마다 N의 시간복잡도가 나오므로 2N의 시간 복잡도가 걸릴 수 있다고 생각할 수 있지만 시간복잡도 계산시 상수는 의미가 없으므로 결국 N의 시간복잡도가 걸린다고 볼 수 있다

투 포인터의 핵심이론

배열에서 알고리즘 상 이중 for문을 사용해야할 경우 하나의 for문을 돌때 하나의 포인터 i 가 배열 전체를 돌며 진행되는 것인데, 이중 for문을 돌게되면 시간복잡도가 너무 커지므로 이 이중 for문의 시간복잡도를 낮추기 위해 첫번째 인덱스 부터 끝의 인덱스까지 진행하는 포인터 1개와 마지막 인덱스부터 첫번째 인덱스까지 진행되는 포인터 1개, 총 2개의 포인터를 두어 시간복잡도를 O(N)으로 해결하는 것입니다

백준 2018 수들의 합

문제 분석

입력된 자연수 N에 대하여 연속된 자연수의 합으로 나타낼 수 있는 가지수를 출력

자연수 N은 1부터 10,000,000 입니다

이중 for문을 돌며 매 구간 별 연속된 합을 나타내기에는 너무 큰 시간 비용이 사용됩니다

이 문제에서는 O(NlogN)으로 해결하여도 시간초과될 확률이 높으므로 O(N) 시간복잡도를 가지는 투 포인터 알고리즘을 사용할 수 있다는 생각을 할 수 있습니다

두개의 포인터를 지정한 후 문제로 접근해보겠습니다

시간복잡도

포인터를 시작인덱스, 끝인덱스로 두어 루프문을 돌때 총 2N 시간소요가 발생하므로 O(N) 시간복잡도가 발생합니다

10,000,000 의 연산횟수라고 가정한다면 약 0.1초의 시간복잡도가 소요된다고 볼 수 있습니다

슈도코드

N 변수 저장

사용 변수 초기화(count =1, start_index = 1, end_index = 1, sum = 1)

while(end_index ≠ N) {

if(sum == N) count 증가, end_index 증가, sum값 변경(index 변경만큼 +)

else if(sum > N) sum값 변경(index 변경만큼 +, start_index 증가

else if(sum < N) end_index 증가, sum값 변경(index 변경만큼 -)

}

정답코드

package org.example;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = null;

        try {
            br = new BufferedReader(new InputStreamReader(System.in));

            StringTokenizer st1 = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st1.nextToken());
            int count = 1;
            int start_index = 1;
            int end_index = 1;
            int sum = 1;

            while (end_index != N) {
                if (sum == N) {
                    count++;
                    end_index++;
                    sum += end_index;
                } else if (sum > N) {
                    sum -= start_index;
                    start_index++;
                } else {
                    end_index++;
                    sum += end_index;
                }
            }
            System.out.println(count);
            }
        catch (Exception e) {
            e.getStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception e) {
            }
        }
    }
}