cpp1 [ALGORITHM] 투 포인터 https://www.acmicpc.net/problem/2003소스코드 사용 문제 투 포인터 알고리즘 1차원 배열에서 포인터를 2개를 이용하여 탐색하는 알고리즘.한번에 2개의 포인터를 이용하기 때문에 그만큼 탐색이 빠르다(O(N)) 투 포인터 알고리즘의 대표적인 문제는 위에서 언급한 문제와 같이 부분합을 구하는 문제이다.부분합을 구하는 문제의 키포인트는부분합이 구하고자 하는 값과 크거나 같으면 start(left) 인덱스를 +1 하고, 작으면 end(right) 인덱스를 -1 하는 것이다. 보통 부분합이라고 하면 누적합 알고리즘. 즉 Prefix Sum을 생각하기 쉽다.그러나, Prefix Sum의 경우 특정 구간의 누적합을 구하는 케이스이고 투 포인터 알고리즘을 이용한 부분합 문제 풀이시에는구간의.. 2024. 12. 7. 이전 1 다음
