📙[Algo] 24.02.06 알고리즘

알고리즘 문제) BOJ 2121. 넷이 놀기

• 링크 : https://www.acmicpc.net/problem/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범위)

접근법

1. 완전탐색으로 접근하기
   • 주어진 좌표들중 4개를 골라 가로A 세로B인 직사각형을 만들 수 있는 지 체크하면 카운팅하기
   • ⇒ 전체 좌표중 4개 선택(4중 for문) 50만50만50만*50만
   • ⇒ !!!!
2. 최적화하기
   • 직사각형 조건
     • 가로변이 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개
           • 오른쪽, 상
           • 오른쪽, 하
           • 왼쪽, 상
           • 왼쪽, 하
     • 생각해보면 8개 점을 모두 찾을 필요 없음.
       • 어차피 저 점들이 결국 주어진 좌표 내에 있어야 된다는 의미니까, 모든 점에서 (x+A, y) (x+A,y+B), (x, y+B)를 찾을 거면 그냥 좌표마다 전 세 좌표도 후보에 존재하는 지 찾으면 되는거다!!!
       • 이걸 모든 좌표마다 이분탐색으로 돌리면 된다.
       • 어렵게 생각해서 너무 오래 걸렸던 문
       • 2차원 좌표 2분 탐색이라고 쫄지 말자!! 그냥 똑같다!

코드

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. 공유기 설치

• 링크 : https://www.acmicpc.net/problem/2110

문제 요약

• 집 N개가 수직선 위에 위치
• 집에 공유기 C개 설치 예정
• 한 집에 하나의 공유기만 설치 가능
• C개의 공유기를 N개의 집에 적당히 설치해서 가장 인접한 두 공유기 사이 거리를 최대로 하기

시간 제한

• 2초

입력

• 집의 개수 N, 공유기 개수 C
  • 2≤N≤20만
  • 2≤C≤N
• N개의 줄에 집의 좌표 xi
  • 0≤xi≤10억

출력

• 가장 인접한 두 공유기 사이 최대 거리 출력

접근법

1 2 4 8 9

1. 완전 탐색
   • for문 C개를 사용해서 설치할 수 있는 모든 경우의 수 탐색
2. 최적화
   • 공유기 수가 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. 용액

• 링크 : https://www.acmicpc.net/problem/2467

문제 요약

• 산성, 알칼리성 용액의 특성값이 주어진다.
  • 산성 : 1 ~ 10억
  • 알칼리성 : -10억 ~ -1
• 두 용액을 혼합할 때 특성값이 0에 가장 가까운 두 용액을 찾을 것

시간 제한

• 1초

입력

• 전체 용액의 수 N
  • 2~10만 자연수
• 용액의 특성값을 나타내는 N개의 정수가 오름차순 입력
  • 모두 다른 값

출력

• 두 용액의 특성값을 합했을 때 0에 가장 가까운 두 용액 찾기

접근법

1. 완전 탐색으로 생각하기
   • 2중 for문을 통해 두 용액을 혼합할 수 있는 모든 경우의 수를 탐색하고 가장 0에 가까운 두 용액 찾기 ⇒ 10만 *10만으로 시간초과!
2. 최적화하기
   • 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();
    }
}