부분합4 [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.∈.bufferedReader()) { val bw = System.out.bufferedWriter() val (n, q) = readLine().split(' ').map { it... 2022. 12. 28. [Kotlin] 백준 1806 : 부분합 문제 링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 해설 부분합과 투 포인터가 결합된 문제다. 부분합에 대한 내용은 아래 포스트를 참고하면 좋다. 링크 : 누적합(Prefix Sum)과 부분합(Partial Sum) with Kotlin 누적합을 저장할 크기가 n+1인 배열을 선언하고 1번째 인덱스부터 누적합을 저장해나간다. 이후 투 포인터를 사용해서 배열 위를 이동하기 시작한다. start부터 end까지의 합이 S 이상이라면 기존 구간 길이의 최소값과 현재 구간 길이.. 2022. 12. 17. 누적합(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=[n1,n2,n3,⋯,nm]와 같은 m 개의 경우에 대해 각 n번째 인덱스까지의 합을 구하는 경우엔 n만큼의 연산을 m 번 반복하게 된다. 즉, 총 시간 복잡도는 O(nm)이 된다. 누적합은 배열의 요소가 변하지 않는다는 점을 이용한다. 원본 배열.. 2022. 12. 17. 이전 1 다음
