투포인터 알고리즘

2003번 - 수들의 합 2

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 투 포인터 알고리즘의 기본적인 문제라고 할 수 있다. 어떻게 보면 이중 반복문을 사용하여 쉽게 풀 수도 있지만 이는 시간 초과가 날 확률이 높으므로 우린 투 포인터 알고리즘 개념을 사용할 것이다. 투 포인터 알고리즘 개념이 익숙치 않다면- https://yhoons.tistory.com/6 투포인터 알고리즘(Two Pointers Algorithm) - c..

투포인터 알고리즘(Two Pointers Algorithm) - c++

투포인터 알고리즘이란? 두 개의 포인터를 각각 이동시키면서 1차원 배열 안 특정 조건에 해당하는 값을 구하는 알고리즘입니다. 알고리즘의 이해 1차원 배열이 있고, 합이 5인 연속적인 부분 수열의 개수를 구하는 문제라고 가정해보겠습니다. 처음 두 개의 포인터는 인덱스 0에 위치해 있고, 각각 start, end 로 구분합니다. ↓ : start ↓ : end ↓↓ 1 2 3 4 5 6 현재 두 포인터 모드 인덱스 0을 가리키고 있으므로 인덱스0부터 0까지의 합은 1입니다. 합을 5로 맞춰야하므로 end 포인터를 오른쪽으로 한 칸 이동시킵니다. ↓ ↓ 1 2 3 4 5 6 현재 start의 인덱스는 0, end는 1을 가리킵니다. 인덱스 0부터 1까지의 합은 3. end포인터를 오른쪽으로 이동 시킵니다. ↓..