Skip to content

Latest commit

 

History

History
executable file
·
101 lines (87 loc) · 2.72 KB

README.md

File metadata and controls

executable file
·
101 lines (87 loc) · 2.72 KB

Two Pointer


두 포인터

  • 두 개의 포인터를 이용해 만족하는 구간을 찾는 알고리즘
  • 상한(high) 조건에 유의할 것
  • 이중 for문을 사용할 경우, 시간복잡도가 O(n2)이지만, 두 포인터를 사용할 경우 시간 복잡도를 O(n)로 줄일 수 있음

연습문제

// https://www.acmicpc.net/problem/2003
#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    static int arr[10'000];
    int n, m;
    cin>>n>>m;
    for (int i = 0; i<n; ++i) {
        cin>>arr[i];
    }

    int res = 0;
    for (int i = 0; i<n; ++i) {
        int sum = 0;
        for (int j = i; j<n; ++j) {
            sum+=arr[j];
            if (sum==m) {
                ++res;
            }
            else if (sum>m) {
                break;
            }
        }
    }
    cout << res;

    return 0;
}
// https://www.acmicpc.net/problem/2003
#include <bits/stdc++.h>

using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    static int arr[10'000];
    int n, m;
    cin>>n>>m;
    for (int i = 0; i<n; ++i) {
        cin>>arr[i];
    }

    int low = 0;
    int high = 0;
    int res = 0;
    int sum = 0;
    while (low<=high) {
        if (sum>m) {
            sum-=arr[low++];
        } 
        else {
            if (sum==m) {
                ++res;
            }
            // 0 1 2 3 '4'
            // if high point to '4' -> break!
            if (high==n) {
                break;
            }
            sum+=arr[high++];
        }
    }
    cout << res;

    return 0;
}

이전 - Binary Search 목록 다음 - Graph