<stdio.han>

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- 파라메트릭 서치

- 이분탐색

[코드]

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 M = Integer.parseInt(st.nextToken());

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        int left = 0;
        int right = -1;
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, trees[i]); // 나무의 최대 높이 이상으로는 자를 수 없기때문에 최대값 구하기
        }

        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            long tree = 0; // 범위를 초과해서 long
            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) {
                    tree += trees[i] - mid;
                }
            }
            if (tree >= M) { // 너무 많이 가져갔거나 정확히 가져갔을 경우
                left = mid + 1;
            } else if (tree < M) { // 너무 적게 가져갔을 경우
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

• 이진 탐색 : 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이. 
• 파라메트릭 서치 : 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘.

이진 탐색은 값들이 주어지고 파라메트릭 서치는 범위가 주어진다.

이진탐색과 비슷하지만 약간 다르다. 솔직히 이해가 정확히 가지는 않는다. 

[참조한 글]

https://loosie.tistory.com/551

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

[난이도]

- Silver 3

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int T, N, M, answer;
    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;

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

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

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int key = Integer.parseInt(st.nextToken());
                answer += binarySearch(key);
            }

            System.out.println(answer);
        }

    }
    static int binarySearch(int key) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            if (key >= arr[mid]) { // key가 mid 와 같거나 클 경우
                left = mid + 1;
            } else if (key < arr[mid]) { // key가 mid 보다 작을 경우
                right = mid - 1;
            }
        }
        // left가 right를 넘어감
        return N - right - 1; 
    }
}

[풀이]

for문을 적게 사용하고 싶어서 B를기준으로 이분탐색을 했다. A가 B를 먹을 수 있는 쌍을 구하는게 아닌 B가 A에게 먹힐 수 있는 쌍을 구했다.

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

[난이도]

- Silver 4

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] arr, answer;
    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;

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

        M = Integer.parseInt(br.readLine());
        answer = new int[M];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            int tmp = upperBound(key) - lowerBound(key);
            bw.write(tmp + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     * key 값이 배열 내에 없을 경우 lowerBound, upperBound 둘다 key 바로 앞의 숫자를 찾게된다. 결국 n - n = 0이 된다.
     */

    static int lowerBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) { // left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치

            /**
             * key 값이 중간 위치의 값보다 작거나 같을 경우
             * 중복 원소일 경우 가장 왼쪽값을 선택
             */
            if (key <= arr[mid]) {
                right = mid;
            } else { // key가 중간 값보다 '클' 경우. key > arr[mid]
                left = mid + 1;
            }
        }
        return left;
    }

    static int upperBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) {// left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치
            if (key < arr[mid]) { // key가 중간 값보다 작을 경우
                right = mid;
            } else { // key가 중간 보다 '크거나' '같을' 경우 key >= arr[mid]
                left = mid + 1;
            }
            // left가 right를 넘어서는 순간 종료된다 == left가 key의 바로 다음 인덱스가 되는순간 종료된다.
        }
        return left;
    }
}

[풀이]

배열안에 중복값이 들어있을 경우가 존재하기 때문에 그 ( 중복값의 가장 왼쪽 인덱스 - 중복값의 가장 오른쪽의 다음 인덱스 ) 를 계산해주어야 한다.

leftBound

찾으려는 key값이 중간 값보다 작거나 클 경우 right 값이 mid가 되고 그 이외의 경우에는 left = mid + 1이 된다.  이를 반복할 경우 left 와 right가 key값들의 가장 왼쪽인덱스가 된다.

rightBound

찾으려는 key값이 중간 값보다 작을 경우 right = mid가 되고 그 외의 경우에는 left = mid + 1이 된다. 이를 반복하다 보면 right는 key값들의 가장 오른쪽 인덱스, left는 key값들의 가장 오른쪽의 다음 인덱스가 된다.

만약 찾으려는숫자가 없을 경우 lowerBound, upperBound 둘다 배열 중 key값을 초과하는 값중 첫 인덱스를 가리키게 된다.

[출처]

https://st-lab.tistory.com/267

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

[난이도]

- Silver 4

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int T, N, M;
    static int[] noteOne;
    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;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            noteOne = new int[N];
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                noteOne[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(noteOne);
            M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            for (int k = 0; k < M; k++) {
                int num = Integer.parseInt(st.nextToken());
                if (binarySearch(num)) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left인덱스가 right인덱스를 넘어가기 전 까지 반복
            int mid = (left + right) / 2;
            if (num > noteOne[mid]) {
                left = mid + 1;
            } else if (num < noteOne[mid]) {
                right = mid - 1;
            } else { // num == noteOne[mid]
                return true;
            }
        }
        return false;
    }
}

[풀이]

가장 기본적인 이분탐색 문제이다. 중요한 점은 출력 시 System.out.println()을 하면 시간초과가 발생한다. 효율이 안좋기 때문에 BufferedWriter를 사용해주자.

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

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] sangArr;
    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;

        N = Integer.parseInt(br.readLine());
        sangArr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            sangArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sangArr); // 오름차순 정렬

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

    static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = N - 1;
        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = sangArr[midIndex];

            if (num < mid) { // 찾으려는 숫자가 더 작을경우 rightIndex를 mid-1 로 설정
                rightIndex = midIndex - 1;
            } else if (num > mid) { // 찾으려는 숫자가 더 클경우 leftIndex mid+1 로 설정
                leftIndex = midIndex + 1;
            } else { // 숫자가 있을 경우
                return true;
            }
        }
        return false; // 숫자가 없을 경우
    }
}

[풀이]

일반적인 이분탐색 문제이다. midIndex와 mid값이 다르기 때문에 탐색은 인덱스 기준으로하고 찾는 숫자는 arr[midIndex]로 찾는다.

https://school.programmers.co.kr/learn/courses/30/lessons/1844

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

import java.util.*;

class Solution {
    static int answer = -1; // 우측하단에 도착하지못할경우 -1출력
    public int solution(int[][] maps) {
        bfs(maps);
        
        return answer;
    }
    static void bfs(int[][] maps){
        int n = maps.length;
        int m = maps[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        int[] dx = {-1, 1, 0, 0}; // 4방탐색
        int[] dy = {0, 0, -1, 1};
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(x == n-1 && y == m-1){ // 우측하단에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++) { // 4방탐색
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 지도 내에 있을 경우
                    if(!visited[nx][ny] && maps[nx][ny] == 1){ // 방문한 적 없고, 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return;
    }
}

[풀이]

일반적인 미로찾기 BFS 알고리즘이다. 

큐에 x좌표, y좌표, 밟은블럭의 수를 담아준다.

queue.offer(new int[]{x, y, count});

• 메서드 이름을 신중히 짓자.
  • 표준 명명 규칙을 따라야 한다. 이해할 수 있고, 일관되게 지어야 한다.
• 편의 메서드를 너무 많이 만들지 말자.
  • 메서드가 너무 많은 클래스는 익히고, 사용하고 문서화하고, 테스트하고, 유지보수하기 어렵다.
• 매개변수 목록은 짧게 유지하자.
  • 4개 이하가 좋다. 4개가 넘어가면 기억하기 쉽지 않다. 같은 타입의 매개변수 여러 개가 연달아 나오는 경우가 특히 해롭다.
• 매개변수의 타입으로는 클래스보다는 인터페이스가 더 낫다.
  • 매개변수로 적합한 인터페이스가 있다면 그 인터페이스를 직접 사용하자. 예를 들어 메서드에 HashMap을 넘길 일은 전혀 없다면 Map을 사용하자.
• boolean보다는 원소 2개 짜리 열거 타입이 낫다.
  • 열거 타입을 사용하면 코드를 읽고 쓰기가 더 쉬워진다.

https://school.programmers.co.kr/learn/courses/30/lessons/159993

[난이도]

- level 2

[알고리즘]

- BFS

[코드]

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

class Solution {
    static char[][] graph;
    static int n, m, answer = 0;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dx = {-1, 1, 0, 0}; // 상, 하
    static int[] dy = {0, 0, -1, 1}; // 좌, 우 4방탐색
    static boolean lever = false;
    public int solution(String[] maps) {
        n = maps.length;
        m = maps[0].length();
        visited = new boolean[n][m];
        graph = new char[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                graph[i][j] = maps[i].charAt(j);
                if(graph[i][j] == 'S'){
                    queue.offer(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }
        bfs();
    
        return answer;
    }
    static void bfs(){
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            } else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 맵 범위 내에 있을 경우
                    if(!visited[nx][ny] && graph[nx][ny] != 'X'){ // 방문한 적이 없고 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        answer = -1;
        return;
    }
}

[풀이]

일반적인 BFS와 같지만 두 가지의 조건을 추가했다.

레버에 처음 도착했을경우 visited 배열을 다시 초기화해준다. 이유는 레버를 켠 후부터는 방문했던칸을 다시 방문해도 되기 때문이다.

queue를 queue.clear()메서드로 모두 비워준다. 레버에 도착한 순간 큐에담겨있던 데이터들은 쓸모없는 데이터들이기 때문이다.

레버를 켰다는 표시인 lever = true; 해준다.

if(!lever&&graph[x][y] == 'L') { // 레버에 도착했을 경우, 레버를 아직 안켰을경우
                visited = new boolean[n][m];
                queue.clear();
                queue.offer(new int[]{x, y, count});
                visited[x][y] = true;
                lever = true;
            }

lever를 켜서 lever = true로 된상태이면서 출구('E')에 도착했을 경우 answer = count; 해준 후 return으로 종료해준다.

else if(lever && graph[x][y] == 'E'){ // 레버를 켠 후 출구에 도착했을 경우
                answer = count;
                return;
            }