누적합3 [Kotlin] 백준 1644 : 소수의 연속합 문제 링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 해설 사용 알고리즘 : 에라토스테네스의 체, 누적합과 부분합, 투 포인터 N이 최대 4,000,000이기 때문에 단순 이중 반복문으로 소수 판정을 하면 시간초과가 발생한다. 따라서 에라토스테네스의 체를 사용하여 소수를 판정해야 한다.(코드의 26~35번째 줄) N 이하의 모든 소수를 판정했다면 이제 N이 소수들의 합으로 나타낼 수 있는지 확인해야 한다. 그런데 문제에서 '연속된 소수의 합'으로 나타낼 수 있는 경우의 수를 구하라는 언급이 있기 때문에 누적합과 투 포인터를 이용한 부분합을 사용하여 이를 효율적으로 구할 수 있다. 소수를 판별한 후 소수의 리스트를 반환.. 2023. 8. 11. [Kotlin] 백준 17390 : 이건 꼭 풀어야 해! 문제 링크 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다. www.acmicpc.net 문제 해설 누적합과 부분합에 대한 기본적인 문제에 정렬이 추가되었다고 볼 수 있다. 입력 받은 배열을 오름차순으로 정렬한 후 각 인덱스에 대한 누적 합 배열을 생성하여 테스트 케이스 별로 \(L\)과 \(R\) 사이의 부분 합을 출력해주면 된다. Code import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val bw = System.out.bufferedWriter() val (n, q) = readLine().split(' ').map { it... 2022. 12. 28. 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합(Prefix Sum) 일반적으로 배열의 \(n\)번째 인덱스까지의 합을 구할 땐 아래와 같이 반복문을 사용하여 계산하게 된다. fun sumOfArray(arr: IntArray, n: Int): Int { var sum = 0 for (i in 0..n) { sum += arr[i] } return sum } 이 경우는 합을 한 번만 구할 때는 문제없이 사용할 수 있으나, \(N=[n_{1}, n_{2}, n_{3}, \cdots, n_m]\)와 같은 \(m\) 개의 경우에 대해 각 \(n\)번째 인덱스까지의 합을 구하는 경우엔 \(n\)만큼의 연산을 \(m\) 번 반복하게 된다. 즉, 총 시간 복잡도는 \(O(nm)\)이 된다. 누적합은 배열의 요소가 변하지 않는다는 점을 이용한다. 원본 배열.. 2022. 12. 17. 이전 1 다음
