투포인터

[baekjoon 15961] 회전 초밥 (슬라이딩 윈도우, 두 포인터) (C++)

https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 회전 초밥처럼 입력된 값을 돌면서 연속해서 먹을 수 있는 K개 중 서로 다른 종류의 초밥이 최대 몇 가지 있을 수 있는지 푸는 문제이다. N이 최대 300만이므로 N^2은 당연히 시간 초과가 난다. 이렇게 K개의 수를 한번 훑어야 하는 경우 보통 슬라이딩 윈도우를 이용하면 O(N)만에 연산을 마칠 수 있다. 또한, 나는 가짓수를 관리해줄 때 map 자료..

[baekjoon 1806] 부분합 (투 포인터) (C++)

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 시간제한이 0.5초로 매우 짧기 때문에, 부분합을 구하기 위해서 2중 for문을 돌면서 풀면 풀리겠지만 시간은 O(N^2)로 시간제한에 걸리게 된다. 따라서 이 문제는 O(N)의 시간 복잡도로 풀이가 가능한 두 포인터를 이용해야 한다. 두 포인터란 배열을 가리키는 포인터 인덱스 l, r (왼쪽, 오른쪽 맘대로)를 선언 후, 매번 조건과 비교하면서 왼쪽, 오른쪽 인덱스를 바꿔주며 배열을 탐색하는 것..