알고리즘/이론
투포인터
오늘은 수들의 합2에서 맞닥뜨린 투포인터 알고리즘에 대해 기록해보고자 한다. 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 1. 투포인터는 어디에 쓰일까? 투포인터가 쓰이는 대표적인 예제로는 [특정한 합을 가지는 부분 연속 수열]을 찾을 때이다. 나는 슬라이딩 윈도우랑 쓰임새가 많이 헷갈렸다. 두 알고리즘의 차이는 투포인터는 구간의 너비가 조건에 따라 유동적으로 변하고, 슬라이딩 윈도우는 구간의 너비가 고정되어 있다는 것이다. 수들의 합2 문제는 고정된 구간의 너비를..
