prefixsum (1) 썸네일형 리스트형 [C++/Algorithm] 투 포인터, 구간 합 이해하기 만약에 문제에서 연속된 데이터 구간을 처리하기를 원한다면 투 포인터 혹은 구간 합을 활용하여 O(n)의 시간 복잡도로 해결할 수 있습니다. 1. 투 포인터 {1, 2, 3, 2, 5} 의 배열이 있고, 연속된 수열의 합이 5인 수열의 개수를 묻는 문제가 있을 수 있습니다. 이러한 문제는 시간에 제한이 없다면 간단하게 for 루프를 중첩시켜 O(n^2)에 해결하는 방법이 있을 수 있습니다. 하지만 인풋 사이즈와 시간 제한으로 인해 O(n^2)의 알고리즘을 사용할 수 없는 경우라면 어떻게 해야 할까요? 그림과 같이 첫 점을 가리키는 두개의 포인터를 선언했다고 가정해 볼게요. 이 상태에서 합이 5 이상이 될 때까지 sum이라는 변수에 값들을 더해주며 End pointer를 우측으로 이동하여 줍니다. 자 Sum.. 이전 1 다음
