two-pointer
-
[BOJ] 2143 두 배열의 합PS/BOJ 2020. 7. 20. 00:06
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 알고리즘: 투포인터 시간복잡도: $O(N^2logN^2)$ 접근: 1. 부 배열은 연속적이다. 2. A 부 배열의 합 + B 부 배열의 합 = T를 만족하는 가짓수 구하기 (합 + 합 = T 가짓수 구하기) -> 2번 조건을 보면 이 문제는 투포인터 문제라는 것을 알 수 있다. 다만 기본적인 투포인터 문제에서 1번 조건의..
-
[BOJ] 1806 부분합PS/BOJ 2020. 7. 16. 19:11
https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘: 투포인터 시간복잡도: O(N) 접근: 1. 연속된 수들의 부분합 -> 연속된 수의 합을 묻는 문제이다. BOJ 1644 소수의 연속합 문제처럼 투포인터로 접근하면 된다. (시작점:st, 끝점:en) 부분합이 S를 넘기면 st++, 길이 갱신(길이의 최솟값 구하기) 부분합이 S보다 작으면 en++ 더보기 #include #include #define MIN(a, b) (((a)>(b))..
-
[BOJ] 1644 소수의 연속합PS/BOJ 2020. 7. 16. 16:43
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 알고리즘: 투포인터, 에라토스테네스의 체 시간복잡도: O(N*log(logN)) 접근: 1. 소수 판별 2. 연속된 합, N 제한( 1번은 에라토스테네스의 체를 이용하면 O(NloglogN) 만에 해결이 가능하다. 문제는 2번인데, 구간 합 문제라고 생각하고 i~j까지 모든 조합을 계산하면, O(N^2)으로 TLE를 받게 ..