[일반] 투포인터 의문

[익명(211.54)]

N개의 리스트를 가지고 진행한다면 right 랑 left 를 가리키는 포인터 두개의 위치를 지정하는 경우의 수가 n C 2 인데, 왜 시간복잡도가 O(N)으로 나오는지 증명을 못하겠어.

먼가 러프하게 left, right가리키는 포인터를 최대한 많이 탐색하는 경우의 수를 고려해 봤을 때 대략 2N이하 인거 같은데... 내가 잘 못해서 투포인터보면 어느정도 그리디한 부분이 있다고 생각하는데, O(N)증명 어디서 볼 수 있는지 아는사람 있어?

[EN_SA(encludingsalt)]

배열요소들을 left right 전부합쳐서 한번씩밖에 안건드리니까

[익명(211.54)]

l,r이 모두 list출발점에서 시작하고 l < r 조건 맞추면서 진행된다고 할때를 잘 모르겠어...

[EN_SA(encludingsalt)]

l이나 r이 잘 진행하다가 갑자기 뒤로 돌아가지는 않잖아

[EN_SA(encludingsalt)]

분할상환분석에 관한 내용이 이해에 도움을 줄지도 모르겠는데

[익명(211.54)]

제가 지금 떠오르는 건 l,r의 경우가 (0,0), (0,1), (0,2), (1,2), (0,3) (1,3) (2,3) ... 이렇게 여러 경우의 수가 있는데, 투포인터 같은 경우는 이 경우의 수를 완전탐색하기 보다는 일정 조건에 의해 경우의 수를 계속 생략하잖아요!! 그런데 정말 최악의 경우를 만났을 때 이를 완전탐색해야한다면 O(N^2)이 뜨지 않을까... 하는 생각이 들어요ㅠ.ㅠ

[익명(211.54)]

도움되는 거 있음 알려주세용 밤 새서라도 읽어볼께요!

[EN_SA(encludingsalt)]

예를들어 (1, 3)이 참이라면 (1, 2)나 (0, 3)같은 뒤로 돌아가는 건 안봐도 참이 되는 그런 상황에서 쓰는 알고리즘이니까

[EN_SA(encludingsalt)]

아님 내가 질문의도를 잘못파악했음 글쓴이는 시간복잡도 자체는 이해할수 있는거 같은데

[익명(211.54)]

그럼 그렇게 코드 내에서의 조건이나 상황에 따라서 탐색을 배제할 수 있기 때문에 조금 러프하게 증명하는 것도 괜찮다는 말씀이실까요?

[EN_SA(encludingsalt)]

문제상에서의 조건이나 상황에 따라서 / 러프하게 증명이 무슨의미인지는 잘모르겠지만 그리디문제풀때 때려맞춰보는 그런느낌이믄 아마 맞을듯

[EN_SA(encludingsalt)]

그리고 전체 탐색해야만 하는 문제는 당연히 투포인터로 안풀리고 그렇게 푸는 문제도 아닐것

[익명(211.54)]

아아 고런 의미 맞습니다. 감사해요!

[익명(223.62)]

Left + Right 값이 1씩 늘어나니까 최악의 경우에도 2N번만 보면 됨

[익명(211.54)]

근데 그게 모든 상황을 포괄할 수 있다는 생각이 안들어요... (0,0), (0,1), (0,2), (1,2), (0,3) (1,3) (2,3) 이렇게 전체를 탐색해야 하는 경우를 만났을 때도 과연 O(N)으로 동작할 수 있을까? 하는 느낌

[자바땔감(coderhs)]

그런 경우는 걍 이중포문이고 투포인터가 아니지

[ㄹㄹ(110.70)]

(1,2)후에 다시 (0,3)을 갈수가없지

[익명(211.219)]

전체탐색해야하는 경우를 배제하기 위해서 정렬된 경우만 사용하는거 아닌가 내가 질문 제대로 이해한게 맞나

[익명(118.235)]

L 과 R은 증가할 때는 독립적으로 증가하니깐 2N이지 이게 증명 끝임 더 자세히 어떻게 증명을 함

[익명(147.47)]

전체 (l,r) 쌍을 다 볼 필요가 없는 경우에만 two pointer를 쓸수 있는 거에요