<stdio.han>

https://www.acmicpc.net/problem/2110

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int result = 0;
        int left = 0;
        int right = arr[N - 1] - arr[0]; // 최대 간격

        while (left <= right) {
            int cnt = 1;
            int cur = arr[0]; // 첫 번째 집부터 시작

            int mid = (right + left) / 2; //공유기 설치의 최소 간격

            for (int i = 1; i < N; i++) { // 첫 번째집은설치했으니 두번째집부터 시작
                if (arr[i] - cur >= mid) {
                    cnt++;
                    cur = arr[i]; // 현재 바라보는 인덱스(커서)를 설치한 집으로 이동
                }
            }

            if (cnt >= C) { // 공유기간의 거리를 적당히 설정해서 최소 C개만큼 설치했을 경우
                result = mid;

                // 좀더 좋은 결과값을 찾기위해 간격을 넓혀본다
                left = mid + 1;
            } else {
                // 결과값을 찾기위해 간격을 좁힌다
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
}

[설명]

공유기를 설치한 집과 다음 설치할 집과의 간격이 mid 이상일 경우에만 cnt를 1씩 증가시킨다. for문이 끝난 후 cnt 의 값이 C이상일 경우 좀더 최적의 해를 찾기위해 간격을 넓혀서 재탐색해본다. 우리는 최댓값을 찾는것이기 때문이다. cnt의 값이 C보다 적을 경우 간격을 좁혀 해를 재탐색한다.

https://www.acmicpc.net/problem/2467

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0;
        int right = N - 1;
        int min = Integer.MAX_VALUE; // 현재 알고있는 최솟값
        int[] answer = new int[2];
        while (left < right) {
            int sum = Math.abs(arr[left] + arr[right]); // 새로운 최솟값
            if (sum < min) { // 새로운 최솟값이 원래 알고있는 최솟값보다 더 작다면 갱신
                min = sum;
                answer[0] = arr[left];
                answer[1] = arr[right];
            }
            if (sum == 0) {
                break;
            }
            if (arr[left] + arr[right] > 0) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

[설명]

간단한 이분탐색 알고리즘 문제이다. 다른 이분탐색 알고리즘과 다른점은 left 와 right 가 arr배열의 인덱스 내에서만 이루어져야만 한다는것을 조심해야한다.

left는 0 (첫번째 인덱스), right는 N - 1 (마지막 인덱스)로 초기화하고 left가 right를 넘어갈때 까지 반복한다.

left 와 right를 더한 값이 0 이상일 경우 right-- 아닐 경우 left ++ 한다.

혹은 0 일경우 바로 출력한다.

https://www.acmicpc.net/problem/1072

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int Z = (int) ((long) Y * 100 / X);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9; // 범위는 문제에서 주어짐
        while (left <= right) { // left가 right를 넘어서면 종료
            int mid = (left + right) / 2;
            int newRate = (int) ((long) (Y + mid) * 100 / (X + mid));
            if (newRate != Z) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

[설명]

이 문제는 이분탐색 문제이다. 처음에 이 문제를 풀 때 오른쪽 끝 범위를 몇으로 정해야 하는지 몰라 잠깐 막혔는데 문제에서 X의 범위는 10억이라고 정해줬다. 간단하게 알고리즘을 설명하자면

1. 범위내의 중간 값 mid 를 초기화해주고 X 외 Y 에 각각 mid를 더했을 때의 승률을 새로 구해준다.

2 - 1. 승률이 변했다면 횟수를 더 줄여야 하기 때문에 right = mid - 1 을 해준다.

2 - 2. 승률이 안변했다면 횟수를 더 늘여야 하기 때문에 left = mid + 1 을 해준다.

생각보다 간단한데 막상 아이디어가 떠오르지 않는다.

https://www.acmicpc.net/problem/1920

[시간초과가 발생한 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        // ArrayList에 값을 담아줌
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            if (list.contains(Integer.parseInt(st.nextToken()))) { // list.contains() 함수를 사용
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[정답코드]

import java.io.*;
import java.util.*;

public class Main {
    public static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 이분탐색은 반드시 정렬이 되어야만 한다.
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            if (binarySearch(Integer.parseInt(st.nextToken())) >= 0) {
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int binarySearch(int key) {
        int low = 0; // 탐색 범위의 왼쪽 끝 인덱스
        int high = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

        // low 가 high 보다 커지면 종료
        while (low <= high) {
            int mid = (low + high) / 2; // 찾는 범위의 중간 값

            if (key < arr[mid]) { // key 가 중간값보다 작을 경우
                high = mid - 1;
            } else if (key > arr[mid]) { // key 가 중간값보다 클 경우
                low = mid + 1;
            } else { // key 가 중간값과 같을 경우
                return mid;
            }
        }
        // 끝까지 탐색했지만 값이 존재하지 않을 경우
        return -1;
    }
}

[설명]

이 문제는 이분 탐색을 활용하면 풀 수 있는문제다. 하지만 처음에 봤을때 간단하게 보여서 list.contains() 메서드를 활용하면 풀릴것같아서 시도해보았다. 결과는 시간초과가 발생했다. 

contains 메서드의 설명을 보면 알 수 있듯이 contains 메서드도 결국에는 리스트의 처음부터 끝까지 탐색하기 때문에 내가 직접 반복문을 시행하나 메서드를 활용하나 별 차이가 없기 때문에 시간초과가 발생했다.

그래서 이분탐색을 활용해 다시 정답을 구해냈다. 코드는 간단해서 설명할것이 없을것 같고 나는 시간복잡도가 궁금해 자료를 검색해봤다.

이러한 일반적인 이분탐색은 거의 대다수가 O(logN) 의 시간 복잡도를 가진다.

N개의 요소를 가진 리스트를 K번 반복한다는 함수를 구한다면 다음과 같다.

운이 좋아 1번만에 찾는다면 (1/2)*N 가 될것이고 3번만에 찾는다면 (1/2)*(1/2)*(1/2)*N 이 될것이다.

운이 안좋아 최악의 경우로  마지막 탐색범위가 1인 경우가 있을수도있다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국  K번 반복한다고했으니 이를 다음과같이 풀어볼 수 있다.

결국 시간복잡도는 O(logN) 이 되는것이다.

원래 내가 작성했던 코드는 간단히 보자면 이중for문이 되는것이기 때문에 시간복잡도는 O(N^2) 혹은 O(NM)이 된다.

https://www.acmicpc.net/problem/2512

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 지방의 수
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " "); // 각 지방의 예산요청
        int left = 0;
        int right = -1; // 예산의 최대 금액
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, arr[i]);
        }
        int M = Integer.parseInt(br.readLine()); // 총 예산
        while (left <= right) {
            int mid = (left + right) / 2;
            long budget = 0;
            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }
            if (budget <= M) {
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        System.out.println(right);
    }
}

[설명]

이 문제는 이분탐색, 매개변수 탐색(파라매트릭 서치)을 활용하는 문제이다. 그 중에 매개변수 탐색을 활용했다. 나는 이분탐색, 매개변수 탐색문제를 풀어본적이없어서 어떻게 접근해야할지 막막해 다른사람이 작성한 글을 참고했다.

매개변수탐색은 주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘이다.

범위는 left 와right로 왼쪽 끝 값과 오른쪽 끝 값을 설정하고 그 범위의 중간값을 계속 찾아내며 조건을 찾아내는 방법이다.

문제를 예로들면 문제의 정답은 127인데 해당 조건을 향해 left 와 right 값을 조정해 나아가는것이다. 처음 left 값은 0 right 값은 150으므로 mid는 75이다. 

반복문을 1회 더 시행하면

이런식으로 left 76, mid 113, right 150 이다. 1회 더 실시하면

left 114, mid 132, right 150 이다.

이런식으로 mid가 해당조건을 넘어서지 못하면 left를 mid + 1로 변경하고 해당조건을 넘어가버리면 right를 mid -1로 설정해나아가면 범위를 좁히는 것이다. 이 문제에서 중요한 점은 해당 지방마다 예산의 한도가 정해져 있기때문에 각 지방의 예산 한도를 넘어서지 않게 주의해야한다. 아래 코드처럼 mid가 해당 지방의 예산보다 작을경우에는 mid를 budget에 추가해주고 지방의 예산을 넘어설 경우에는 해당 지방의 최대예산을 추가해준다.

            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }