생각하는 아져씨

2559번: 수열https://www.acmicpc.net/problem/2559문제 정의어떤 정수의 수열이 주어졌을 때, 연속적인 며칠 동안의 숫자의 합이 가장 큰 값이 무엇인지 알아보는 문제이다. 접근 방법Naive 한 방법온도 리스트를 순회하면서 K만큼 해당하는 부분 리스트의 합을 구한다. → 최대 O(N2)O(N^2)O(N2) 이다.그 합들 중에서 가장 큰 부분 합을 리턴한다. 최대 O(N) 이다.따라서 시간 초과 발생하므로, 누적합을 이용해 효율적으로 풀 수 있다. 누적합을 이용한 방법온도 리스트를 순회하면서 누적합을 구해서 prefix_sum 리스트에 저장한다.K만큼 해당하는 구간 리스트의 합은 누적합의 성질을 이용해서 구할 수 있는데, 예를 들어 (5, 6, 7, 8)의 합을 구하고 싶다면..

개요누적합누적합 예제 문제 살펴보기2차원 배열에서 누적합구현간단한 구현 예제구현 시 고려해야 할 메모리 제약 사항 (Python)채점 환경 (Python)문제를 푸는 방법참조 개요오늘은 알고리즘의 가장 첫번째인 누적합과 구현에 대해서 공부한다. 이 글은 세상을 널리 이롭게 하는 돌, 큰 돌 님의 강의를 기반으로 정리하고 개인적으로 공부한 것을 덧붙여 정리하였음을 먼저 밝힌다. 공부를 할 때 마다 새로운 지식을 계속해서 정리할 예정이다.누적합누적합이란 요소들의 누적한 합을 의미한다.어떤 배열을 기반으로 앞에서 부터 요소들의 누적한 합을 저장해서 새로운 배열을 만들고 이를 활용하는 방식이다. 누적합의 종류에는prefix sum: 앞에서부터 더하는 것 → 코딩테스트에 나오는 것suffix sum: 뒤에서부터 ..