본문 바로가기
728x90

알고리즘(w.KOTLIN)/구간 합

 (2)
[알고리즘][KOTLIN] 우박수열 정적분 https://school.programmers.co.kr/learn/courses/30/lessons/134239 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 입력의 초항(k) 가 1이 되는 과정인 우박수열을 저장하는 arr 배열선언하고 주어진 조건에 따라 값을 저장한다. 2. 각 구간의 사다리꼴 면적을 구해 area 배열에 저장한다. 3. 구간 합을 sum 배열에 저장한다. 구간 합 알고리즘 => sum[i] = sum[i - 1] + area[i] 4. ranges 배열을 탐색하여 a, b 값을 찾고 start, end 값을 구한다..
[알고리즘][KOTLIN] 구간 합 구간 합 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 0번째부터 i 번째까지의 합을 구하는 공식 - S[i] = A[0] + A[1] + A[2] + … + A[i - 1] + A[i - 2] - 배열 A [15, 13, 10, 7, 3, 12] - 합 배열 S [15, 28, 38, 45, 48, 60] S[i] = S[i - 1] + A[i] i번째부터 j번째까지의 합을 구하는 공식(구간 합) S[j] - S[i - 1] 배열이 변경될 경우 -> 세그먼트 트리를 사용한다. 문제 주어진 배열에서 k 개수 만큼 연속된 원소를 추출하여 새로운 배열을 만들었을 때 만들어진 새로운 배열 중 최대값을 구하여라 입력 배열 : [10, -4, 3, 1, 5, 6, -35, 12..

티스토리툴바