[필수 알고리즘] 투포인터

투포인터란?

- 각 원소마다 모든 값을 순회해야할때, o(n^2)

- 연속하다는 특성을 이용해 처리, O(N)

- 두개의 포인터(커서)가 움직이면서 계산

 

처음 아이디어

- for문으로 각 숫자의 위치에서 이후 K개의 개수를 더함

- 이때마다 최대 값으로 갱신

 

처음 시간 복잡도

- for문 : O(N)

- 각 위치에 K개의 값 더함: O(K)

- 총 : O(NK)

 

아이디어

- 처음 K개의 값을 구함

- for문: 다음 인덱스의 값을 더하고, 앞의 값을 뺌

- 이때 최대값을 갱신

 

시간 복잡도

- 숫자 개수만큼 for => O(N)

 

자료구조

- 전체 정수 배열: int[]

- 합한 수 : int

 

문제풀이

- 백준 2559

 

1.

public class num_2559
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);

        string[] input_ = Console.ReadLine().Split();
        int[] nums = Array.ConvertAll(input_, int.Parse);
    }
}

- 입력 관련 처리

 

2. 

int each = 0;
for (int i = 0; i < K; i++)
{
    each += nums[i];
}
int maxv = each;

- K개의 합을 구하기 위해 each 변수 후 더하주기

- K개의 합을 구하지 않으면 매번 새로운 K개의 합을 구하기 위해 K번 덧셈 연산을 필요로함

- 즉, each를 구해두면 O(N)이지만 없다면 O(K*N)이 됨

 

3.

for (int i = K; i < N; i++)
{
    each += nums[i];
    each -= nums[i - K];
    maxv = Math.Max(maxv, each);
}

Console.WriteLine(maxv);

- 시작 값을 K로 하여 N보다 작은 모든 정수를 한칸씩 순회하며, 최대값을 찾는데 사용

 

최종코드

/*
1. 아이디어
- 투포인터 활용
- for문으로, 처음 k개값 저장
- 다음 인덱스 더하고, 이전 인덱스 빼줌
- 이때마다 최대값 갱신

2. 시간복잡도
- O(N) => 1e5 > 가능 

3. 자료구조
- 각 숫자들 N개 저장 배열 : int[] (숫자들 최대 100 > INT가능)
- K개의 값을 저장 변수 : int (최대 : K * 100 = 1e5 * 100 > INT가능)
- 최대값 : int
*/


public class num_2559
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);

        string[] input_ = Console.ReadLine().Split();
        int[] nums = Array.ConvertAll(input_, int.Parse);

        //k개 더해주기
        int each = 0;
        for (int i = 0; i < K; i++)
        {
            each += nums[i];
        }
        //each가 없다면 매번 새로운 k개의 합을 구할때마다 k번의 덧셈하는 연산 필요
        //즉, O(N)이 아닌 O(K*N)이 되버림
        int maxv = each;

        // 다음인덱스 더해주고, 이전인덱스 빼주기
        for (int i = K; i < N; i++)
        {
            each += nums[i];
            each -= nums[i - K];
            maxv = Math.Max(maxv, each);
        }

        Console.WriteLine(maxv);
    }
}

 

참고영상

- 바로가기