two pointer12 백준 1644 자바 - 소수의 연속합 (boj 1644 java) 문제 : boj1644 소수의 연속합인걸 일단 생각 안하고 그냥 어떠한 자연수로 이루어진 배열이 있고, 연속한 배열의 부분합이 N인걸 찾는다고 생각해보자. 일단 단순히 모든 범위를 보려면 O(N^2) 이므로 통과할 수 없다. 그렇다고 DP로 풀자니 식이 잘 떠오르지 않았다. 보통 이런류의 연속합은 투포인터를 활용하면 쉽게 찾을 수 있다(원래는 통과할 방법 찾기 전에 대충 어떠한 수가 소수의 연속합으로 몇 번 정도 나오는지 궁금해서 대충 짜보고 돌린건데 통과했다 ㅋㅋ). 투포인터 전략만 잘 세우면 된다. st와 ed라는 두 포인터를 두고 [st, ed] 구간에 포함된 합을 계속 계산하고 있다고 해보자. 시작은 st와 ed 둘 다 배열의 첫번째에 둔다. 이 경우 ed가 증가(다음 칸으로 전진)되면 합이 늘어.. 2022. 4. 5. 백준 2467 자바 - 용액 (BOJ 2467 JAVA) 문제 : boj2467 1. 당연히 모든 쌍을 확인해보면 O(N^2)이 걸릴 것이므로 통과가 불가하다. 이 문제는 투 포인터 알고리즘으로 풀 수 있는 기본형 문제이다. 또는 안풀어보긴 했으나 이분탐색으로도 문제없이 풀 수 있을 것 같다(N개를 TreeSet에 넣어둔 후 N개의 값을 순회하며 해당 값에 -1을 곱한 값에 대해 TreeSet에서 ceilling과 floor를 확인해 그 중 작은 수를 택하면 될 듯함). 2. 이미 정렬되어 들어온 데이터 이므로 정렬과정 필요 없이 첫번째 값을 s로 가르키고, 맨 뒤의 값을 e로 가르켜보자. 이제 s와 e가 가르키는 값을 합쳐가며 이 중 0과 가장 가까운 값을 찾으면 된다. s와 e를 변경하는 규칙은 다음과 같다. arr[s]+arr[e] == 0 -> 바로 출.. 2022. 1. 20. 이전 1 2 다음
