[일반] 투포인터 역전

[익명(61.74)]

투포인터에서 두 포인터가 역전되지 않음을 어떻게 증명하지

루프불변식 버무려서 잘 정리된 글 없나연

풀긴풀었는데 때려맞춘느낌이야 헷갈려 쓰읍

[Bubbler(bubbler)]

투포인터가 움직이는 방법은 문제마다 다르니까 문제를 알려줘야 증명할수 있음 - dc App

[익명(61.74)]

l=0,r=0으로 놓고 조건에 맞으면 r 증가, 조건에 안맞으면 l 증가 1. l==r인 경우에는 구간이 비어있다. 2. r은 구간의 다음을 가리킨다. 로 생각했는데 먼가 억지스러움....

[Bubbler(bubbler)]

그거는 구간이 비어있을때 항상 조건에 맞으면 되겠네 - dc App

[익명(apg2fwpfgsz5)]

그거 자동으로 성립되는게 아니지 않나? 문제의 조건에 따라서 성립하거나, 코드로 직접 명시해야 했던거 같은디

[익명(61.74)]

모르겠음