[C#][프로그래머스] 연속 부분 수열 합의 개수 프로그래머스 > 코딩테스트 연습 > 연습문제 > 연속 부분 수열 합의 개수 https://school.programmers.co.kr/learn/courses/30/lessons/131701 📒 문제철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다. 원형 수열의 모든 원소 elements가 순서대로 주어질.. 2025. 2. 10. [알고리즘] 누적합 (Prefix Sum) 누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배열에 저장해 두는 것이다. 이후 특정 구간의 합을 구할때 저장해둔 배열을 사용한다. 더보기동적계획법(DP, Dynamic Programming)여기서 동적계획법을 간단히 설명하면 DP, 즉 Dynamic Programming의 줄임말로 기본적인 아이디어는 하나의 큰문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.DP는 특정한 알고리즘이 아닌 문제해결 패러다임으로 해당 이름은 큰 의미가 없이 지어졌다고 한다. 누적합 조건 누적합은 배열의 값들이 변.. 2025. 2. 10. 이전 1 다음
