구간합2 [Java/백준/투포인터] 1806번: 부분 합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 연속된 수들의 부분합들 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성해야 한다. 참고한 부분은 아래 링크! https://dev2som.tistory.com/135 [Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간.. 2021. 6. 25. [Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간합 알고리즘에 대해 알아보려 한다. 수열에서 합이 N인 연속부분수열 → Two Pointer N개의 정수로 구성된 수열에서 M개의 쿼리에 해당하는 구간합 → Interval Sum 코테에서도 많이 나오는 것 같다. 특정한 합을 가지는 부분 연속 수열 찾기 [투 포인터를 활용한 알고리즘 설명] 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 현재 부분 합이 M과 같다면, 카운트한다. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 양의 .. 2021. 6. 24. 이전 1 다음
