📙 Algorithm Solving/Java
📙[Algo] 24.02.06 알고리즘
혜덕hyeduck
2024. 2. 7. 08:56
알고리즘 문제) BOJ 2121. 넷이 놀기
문제 요약
- 2차원 평면 → N개의 점
- 네 사람이 점을 1개씩 선택해서 변이 x축, y축에 평행한 직사각형 만들 것
- 가로 길이 A, 세로 길이 B인 직사각형을 얼마나?
시간 제한
- 2초
입력
- 점들의 개수 N (5≤N≤50만)
- 만들고 싶은 직사각형의 가로 길이 A B
- 1 ≤ A ≤ 1000
- 1 ≤ B ≤ 1000
- N개의 좌표들이 주어짐
- -10억 ~ 10억
- 각각 다르다
출력
- 가능한 모든 경우의 수 출력
- 2^31-1보다 작거나 같음(int범위)
접근법
- 완전탐색으로 접근하기
- 주어진 좌표들중 4개를 골라 가로A 세로B인 직사각형을 만들 수 있는 지 체크하면 카운팅하기
- ⇒ 전체 좌표중 4개 선택(4중 for문) 50만50만50만*50만
- ⇒ !!!!
- 최적화하기
- 직사각형 조건
- 가로변이 x축에 평행
- 세로변이 y축에 평행
- 즉, (x1,y1), (x2,y2), (x3,y3), (x4,y4)가 선택되었다면
- x1==x2, x3==x4
- y1==y3, y2==y4
- x3~x1 == A, y2~y1 == B
- for문은 하나만 쓸 수 있다.
- 점을 하나 선택하면(x,y)
- 나머지 점들은
- x좌표가 같고, y좌표 차이가 B인 친구 → 2개
- 오른쪽(+)
- 왼쪽(-)
- x좌표 차이가 A이고, y좌표가 같은 친구 → 2개
- 상(+)
- 하(-)
- x좌표 차이가 A이고, y좌표 차이가 B인 친구 → 4개
- 오른쪽, 상
- 오른쪽, 하
- 왼쪽, 상
- 왼쪽, 하
- x좌표가 같고, y좌표 차이가 B인 친구 → 2개
- 나머지 점들은
- 생각해보면 8개 점을 모두 찾을 필요 없음.
- 어차피 저 점들이 결국 주어진 좌표 내에 있어야 된다는 의미니까, 모든 점에서 (x+A, y) (x+A,y+B), (x, y+B)를 찾을 거면 그냥 좌표마다 전 세 좌표도 후보에 존재하는 지 찾으면 되는거다!!!
- 이걸 모든 좌표마다 이분탐색으로 돌리면 된다.
- 어렵게 생각해서 너무 오래 걸렸던 문
- 2차원 좌표 2분 탐색이라고 쫄지 말자!! 그냥 똑같다!
- 점을 하나 선택하면(x,y)
- 직사각형 조건
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int A, B;
static int[][] arr;
static int answer = 0;
static boolean binarySearch(int x1, int y1) {
int s = 0, e = N - 1, mid, x2, y2;
while (s <= e) {
mid = (s + e) / 2;
x2 = arr[mid][0];
y2 = arr[mid][1];
if (x1 < x2 || (x1 == x2 && y1 < y2)) {
e = mid - 1;
} else if (x1 > x2 || (x1 == x2 && y1 > y2)) {
s = mid + 1;
} else {
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
arr = new int[N][2];
st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (o1, o2) -> {
if(o1[0] == o2[0]) return o1[1] - o2[1];
else return o1[0] - o2[0];
});
for (int i = 0; i < N; i++) {
if (binarySearch(arr[i][0] + A, arr[i][1] + B)
&& binarySearch(arr[i][0] + A, arr[i][1])
&& binarySearch(arr[i][0],arr[i][1] + B)) {
answer++;
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2110. 공유기 설치
문제 요약
- 집 N개가 수직선 위에 위치
- 집에 공유기 C개 설치 예정
- 한 집에 하나의 공유기만 설치 가능
- C개의 공유기를 N개의 집에 적당히 설치해서 가장 인접한 두 공유기 사이 거리를 최대로 하기
시간 제한
- 2초
입력
- 집의 개수 N, 공유기 개수 C
- 2≤N≤20만
- 2≤C≤N
- N개의 줄에 집의 좌표 xi
- 0≤xi≤10억
출력
- 가장 인접한 두 공유기 사이 최대 거리 출력
접근법
1 2 4 8 9
- 완전 탐색
- for문 C개를 사용해서 설치할 수 있는 모든 경우의 수 탐색
- 최적화
- 공유기 수가 N개, N은 최대 20만까지 가능하므로, 모든 경우를 설치하면 안 됨.
- 가장 가까운 공유기 사이 거리가 최대가 되어야 함!
- 결국 다른 사람 풀이 참고했는데,, 이해가 안 된다.
- 나는 무조건 집에만 설치해야 된다고 생각했는데, 왜 end 값을 x[N-1]-x[0], start값을 0으로 잡아서 mid값을 설정해서 거리 비교한걸까..,,,
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, C;
static int[] x;
static int answer = Integer.MIN_VALUE;
static void binarySearch(int s, int e) {
int mid, cnt, installed;
while (s <= e) {
mid = (s + e) / 2;
installed = x[0];
cnt = 1;
for (int i = 1; i < N; i++) {
if (x[i] - installed >= mid) {
cnt++;
installed = x[i];
}
}
if (cnt >= C) {
answer = Math.max(answer, mid);
s = mid + 1;
} else {
e = mid - 1;
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
x = new int[N];
for (int i = 0; i < N; i++) {
x[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(x);
binarySearch(0, x[N - 1] - x[0]);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 2467. 용액
문제 요약
- 산성, 알칼리성 용액의 특성값이 주어진다.
- 산성 : 1 ~ 10억
- 알칼리성 : -10억 ~ -1
- 두 용액을 혼합할 때 특성값이 0에 가장 가까운 두 용액을 찾을 것
시간 제한
- 1초
입력
- 전체 용액의 수 N
- 2~10만 자연수
- 용액의 특성값을 나타내는 N개의 정수가 오름차순 입력
- 모두 다른 값
출력
- 두 용액의 특성값을 합했을 때 0에 가장 가까운 두 용액 찾기
접근법
- 완전 탐색으로 생각하기
- 2중 for문을 통해 두 용액을 혼합할 수 있는 모든 경우의 수를 탐색하고 가장 0에 가까운 두 용액 찾기 ⇒ 10만 *10만으로 시간초과!
- 최적화하기
- for문을 하나밖에 못 쓴다.
- 용액을 하나 선택하고 ⇒ 나머지 용액을 돌면서 이진탐색하며 후보를 거른다.
- -4 -3 -2 -1 2
- -4 선택
- 정중앙 값 -2와 비교해서 더했을 때 값 일단 기록, -4는 음수이고, 중앙 값도 음수 이기 때문에 -2 왼쪽에 있는 친구들은 아예 배제
- 정중앙 값 -1와 비교해서 더했을 때 값 기록, -4는 음수 이고, 중앙 값도 음수 이기 때문에 -1 왼쪽에 있는 친구들 배제
- 정중앙 값 2와 비교해서 더했을 때 값 기록, ⇒ 마지막
- 여기서 후보를 어떻게 제거하는지를 봐야 하는데 음수의 경우 음수인 후보들의 절대값이 작을수록, 양수인 후보들의 경우 음수의 절대값에 가까울 수록 차이가 작아진다.
- 양수의 경우 양수인 후보들의 절대값이 작을수록, 음수인 후보들의 경우 절대값을 취했을 때 양수의 절대값에 가까울 수록 차이가 작아진다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int answer = Integer.MAX_VALUE;
static int[] ansValue = new int[2];
static void binarySearch(int s, int e, int key, int[] arr) {
int mid;
while (s <= e) {
mid = (s + e) / 2;
if (key < 0) {
// key가 음수인 경우
if (arr[mid] < 0) {
// 비교하려는 후보로 음수가 선택 됐을 때, 해당 후보 왼쪽은 무조건 제거
s = mid + 1;
} else {
// 비교하려는 후보로 양수가 선택 됐을 때,
// 선택된 key값의 절대값보다 해당 후보가 클 경우 오른쪽 후보들은 제거
// 선택된 key값의 절대값보다 해당 후보가 작을 경우 왼쪽 후보들을 제거
if(Math.abs(key) < arr[mid]) e = mid - 1;
else s = mid + 1;
}
} else {
// key가 양수인 경우
if (arr[mid] > 0) {
// 비교하려는 후보로 양수가 선택 됐을 때, 해당 후보 오른쪽은 무조건 제거
e = mid -1;
} else {
// 비교하려는 후보로 음수가 선택 됐을 때,
// 선택된 key값의 절대값보다 해당 후보의 절대값이 클 경우 왼쪽 후보들은 제거
// 선택된 key값의 절대값보다 해당 후보의 절대값 작을 경우 오른쪽 후보들을 제거
if(key > Math.abs(arr[mid])) e = mid - 1;
else s = mid + 1;
}
}
if (key != arr[mid] && answer > Math.abs(arr[mid] + key)) {
answer = Math.abs(arr[mid] + key);
ansValue[0] = key;
ansValue[1] = arr[mid];
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] values = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
values[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
binarySearch(0, N-1, values[i], values);
}
Arrays.sort(ansValue);
bw.write(String.valueOf(ansValue[0] + " " + ansValue[1]));
bw.flush();
bw.close();
br.close();
}
}