[리뷰] 해결 못한 알고리즘 다시 풀기 -5

1. 이분 검색

•  조건
  1. 중복값이 존재하지 않는다
  2. 정렬된 상태여야 한다.

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int [] arr = new int[n];
    for(int i=0;i<n;i++){
      arr[i]=in.nextInt();
    }
    System.out.println(solution(n, m, arr));
  }
  static int solution(int n, int m, int[] arr){
    int answer=0;
    Arrays.sort(arr);
      int lt=0;
      int rt=arr.length-1;
    while(lt<=rt){
      int mid=(lt+rt)/2;

      if(arr[mid]==m)
        return answer=mid+1;
      else if(arr[mid]<m){
        lt=mid+1;
      }
      else if(arr[mid]>m){
        rt=mid-1;
        answer=rt;
      }
    }
    
    return answer;
  }
                       
}

---

 

2. 뮤직비디오 (결정알고리즘)

• 조건
  1. 같은 크기 DVD, M개에 곡들이 순서대로
  2. 가능한 최소 용량 : 가장 큰 1곡의 길이
     가능한 최대 용량 : 모든 곡의 길이 합
  3. 최소로 가능한 용량을 찾는다 -> 가능한 값인지 체크하기
  4. m개의 디스크에 mid분으로 담을 수 있는지 확인하는 함수 만들기

import java.util.Scanner;

public class Main {

	static boolean check(int mid, int[] arr) {
		int sum = 0;
		int cnt = 1;
		boolean flag = true;
		for (int i = 0; i < n; i++) {
			sum += arr[i];
			if (sum > mid) {
				sum = arr[i];
				cnt++;
				if (cnt > m)
					return flag = false;
			}
		}
		return flag;
	}

	static int lt, rt, n, m;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		int[] arr = new int[n];
		lt = Integer.MIN_VALUE;
		rt = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
			lt = Math.max(lt, arr[i]);
			rt += arr[i];
		}
		System.out.println(solution(arr));
	}

	static int solution(int[] arr) {
		int answer = 0;
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (check(mid, arr)) {
				rt = mid - 1;
				answer = mid;
			} else
				lt = mid + 1;
		}
		return answer;
	}
}

---

 

3. 마구간 정하기 (결정 알고리즘)

• 조건
  1. 주어진 마구간 n개에 m마리의 말을 배치
  2. nCm개의 가짓수가 존재
  3. 최대한 떨어지도록 배치한다.
  4. 이분 검색을 활용하기 위해 정렬을 수행
  5. 가능한 최소 거리 : 1
     가능한 최대 거리: (마구간 위치의 최댓값) - (마구간 위치의 최솟값)
  6. 최대로 가능한 거리를 찾는다.
  7. n개의 마구간의 최소거리가 mid로 배치시킬 수 있는지 확인하는 함수 만들기

 

import java.util.*;

public class Main {
	static int[] arr;
	static int n, m;

	static boolean check(int mid) {
		boolean flag = true;
		int cnt = 1;
		int ep = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (arr[i] - ep >= mid) {
				cnt++;
				ep = arr[i];
				if (cnt == m)
					return flag;
			}
		}
		return flag=false;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		System.out.println(solution(n, m));
	}

	static int solution(int n, int m) {
		Arrays.sort(arr);
		int answer = 0;
		int lt = 1;
		int rt = Arrays.stream(arr).max().getAsInt() - Arrays.stream(arr).min().getAsInt();
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (check(mid)) {
				lt = mid + 1;
				answer = mid;
			} else {
				rt = mid - 1;

			}
		}
		return answer;
	}
}

---

4. 계단오르기

5. 돌다리 건너기

6. 최대 부분 증가 수열 [LIS 알고리즘]

7. 가장 높은 탑 쌓기

8. 동전교환 (냅색 알고리즘)