📍문제 링크 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 📍알고리즘 분류 - 누적 합 - 투 포인터 - 슬라이딩 윈도우 📍문제 풀이 수열이 주어지고 1 이상 수열의 길이 이하인 자연수 K가 주어질 때, 수열에서 K연속 숫자들의 합의 최대값을 구하라 이 문제는 간단하지만, 수열의 길이가 10만 까지 가능하기 때문에 O(N^2) 로는 해결할 수 없다 누적 합 (prefix sum) 을 이용하면 O(N) 에 빠르게 해결할 수 있다 1..

📍문제 링크 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 📍알고리즘 분류 - 다이나믹 프로그래밍 - 누적 합 📍문제 풀이 - 연속된 수열이 주어지고, 1 ~ 3 사이의 자연수 max가 하나 주어진다 - 연속된 수열에서 max 개의 연속하는 수를 3개 만들고, (겹치면 안됨) 그 합이 최대가 되는 수를 구하라 ⭐연속된 수열에서 구간 합을 빠르게 구하기 위해 누적 합 (prefix sum) 배열을 만들고 이용한다 - 예를 들어 1 2 3 ..