반응형 투포인터2 프로그래머스 연속된 부분 수열의 합 - C++ 풀이 1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자. 2. sum(lo, hi) k 이면 lo를 늘린다. 1. 투포인터를 사용한다. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라 하자. 부분 수열의 시작과 끝 인덱스를 각각 lo, hi라고 두자. 수열이 비내림차순으로 정렬되어 있기 때문에 hi를 늘리면 무조건 sum(lo, hi)는 증가한다. 또한 모두 양수이므로 lo를 늘리면 무조건 sum(lo, hi)는 감소한다. 따라서 투포인터를 사용하여 O(N)에 해결할 수 있다. lo = 0, hi = 0인 경우부터 시작한다. 2. sum(lo, hi) < k 이면 hi를 늘린다. sum(lo, hi) < k이면 부.. 2023. 9. 5. 백준 1644번 소수의 연속합 - 스위프트(Swift) 풀이 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다. 일단 소수들을 구해야 한다. N=4,000,000이므로 4,000,000 이하인 소수 목록을 다 구한다. 에라토스테네스의 체를 사용하면 O(NloglogN)에 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. 그리고 나서 소수들만 추려 배열을 만든다. 2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다. 연속하는 모든 구간을 탐색하는 것은 불가능하다. 소수 개수(M)가 약 280,000개 이므로 O(M^2)의 시간 복잡도로는 .. 2022. 2. 3. 이전 1 다음 반응형
