투포인터

📖 문제 https://www.acmicpc.net/problem/2118   💡  풀이 방식• 누적합, 투 포인터 N가지 지점 中 2가지를 뽑는 경우의 수는 N * (N-1)/2이고, 이러면 약 12억 5천만을 넘으므로 시간 초과가 발생한다.그러므로 투 포인터로 두 지점을 뽑는다. 그리고 나서 정방향 / 역방향으로 진행하며 최대 거리를 구한다.   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243import java.util.*;import java.io.*; public class Main {    public static void main(String[] args) throws IOException..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; class Solution { public int[] solution(int[] sequence, int k) { int[] answer = new int[] {0, sequence.length - 1}; int left = 0; int right = 1; int sum = s..

🔺 문제 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..

🔺 문제 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 🔺 코드 1) 누적 합 풀이 - 시간 복잡도 : O(N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..

🔺 문제 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException..

🔺 문제 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOExceptio..

🔺 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buff..

🔺 문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.util.*; import java.io.*; public class Main { public static void main(String[] args)..

📍 연속합 정의 주어진 수열에서 연속된 부분 수열의 합 중 최댓값을 구하는 문제 📍 해결 방법 ① DP ◾ WHEN? 입력 크기가 작은 경우 ◾ HOW? 이전 부분 수열의 합에 현재 수를 더하면서 최댓값 업데이트 (점화식 : 현재 수를 더할 것인지 or 현재 수부터 새로운 부분 수열을 시작할 것인지 결정) ② 투 포인터 ◾ WHEN? 입력 크기가 큰 경우 & 수열 순서가 중요한 문제 (수열의 순서를 유지하며 부분 수열을 구할 수 있으므로) ◾ HOW? 시작 포인터와 끝 포인터를 조정하면서 합을 계산하고, 최댓값 업데이트 ➕ 예제 [백준/JAVA] 1644번: 소수의 연속합 🔺 문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net..