본문 바로가기
  • 개발하는 곰돌이

부분합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.`in`.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=[n_{1}, n_{2}, n_{3}, \cdots, n_m]\)와 같은 \(m\) 개의 경우에 대해 각 \(n\)번째 인덱스까지의 합을 구하는 경우엔 \(n\)만큼의 연산을 \(m\) 번 반복하게 된다. 즉, 총 시간 복잡도는 \(O(nm)\)이 된다. 누적합은 배열의 요소가 변하지 않는다는 점을 이용한다. 원본 배열.. 2022. 12. 17.