https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] numbers, int m){ int right = 0; int min_diff = 2_000_000_000; for(int left=0; left
Problem Solving
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int search(int[] acc, int s){ int right = 0; int sum_length=acc.length+1; for(int left=1; left
투 포인터 (주로) 선형 데이터 구조에서 두 개의 인덱스를 관리하여 특정 조건을 만족하는 부분집합이나 특정 값을 찾는 알고리즘 1. 두 포인터(인덱스)를 시작점(left=0, right=0 또는 left=0, right=마지막인덱스 또는 서로다른 배열 등)으로 초기화한다. 2. 규칙에 따라 포인터를 이동시킨다. - 같은 배열에서 동일한 방향으로 이동하는 투 포인터 - 같은 배열에서 마주보는 방향으로 좁혀가는 투 포인터 - 서로 다른 배열에서 이동하는 투 포인터 - 여러 형태에서 효율적인 시간 복잡도를 가진다. 3. 두 포인터 중 하나 혹은 둘 모두가 끝에 도달할 때까지 반복한다. * 인덱스가 아니더라도 오른쪽(시계방향), 왼쪽(반시계) 거리를 right, left로 둘 수 도 있다. https://yun..
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 이문제는 Map과 이분탐색 두가지 방법으로 풀 수 있다. 나는 Map이 더 간단해보여 Map을 이용했다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ Bu..
https://www.acmicpc.net/problem/2792 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net check()함수 만드는 것이 꽤 생각을 요하는 문제 질투값이 널널하다면 그냥 true을 뱉으면 된다. 왜냐면 다음 탐색에서 정답을 찾기 때문에 최대한 빡세게 검사하고 보석을 다시 분배에서 사람수만큼의 집합으로 만든다고 생각하면됨 다시 문제를 보니 보석을 주지 않아도 되기 때문에 간단한 문제였다.. import java.util.*; import java.io.*; public class Main ..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net check함수의 반복문 처음에 각 영상이 디스크크기를 초과할 경우가 있다는 것을 확인해주지 않아서 풀이시간이 꽤 걸렸다. import java.util.*; import java.io.*; public class Main { public static int n; public static int m; public static int[] input; public static boolean check(int ..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int n; public static int limit; public static int[] input; public static boolean check(int num){ int sum=0; for(int i=0; i
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int n; public static int m; public static Integer[] houses; public static boolean check(int dist){ int count =1; int cur =..
