[이것이 코딩 테스트다 with Python]_27_이진 탐색 문제풀이

220209 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=jjOmN2_lmdk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=27 

 

 

 

 

1. 파라메트릭 서치 (Parametric Search)

: 최적화 문제를 결정 문제 (예 or 아니오) 로 바꾸어 해결

( 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 )

 

 

 

< 문제1 > 떡볶이 떡 만들기

: 절단기에 높이(H) 를 지정하면, 줄지어진 떡을 한 번에 절단

: 높이가 H 보다 긴 떡은 H 위의 부분이 잘리고, 낮은 떡은 잘리지 않음

: 손님은 잘린 떡 길이를 가져감

: 손님이 요청한 총 길이가 M 일 때, 적어도 M만큼의 떡을 얻기 위해, 절단기에 설정할 수 있는 높이의 최댓값

 

- 적절한 높이를 찾을 때까지 이진 탐색 수행하여 높이 H 반복해서 조정

- 조건을 만족한 뒤에, 조건의 만족 여부에 따라서 탐색 범위 좁힘

- 큰 탐색 범위는 이진 탐색 !!!

 

1) 필요한 떡 길이 M = 6

2) 시작점 0, 중간점 9, 끝점, 19      => 25.... SO BIG

3) 시작점 15, 중간점 19, 끝점, 17     =>2....  BIG

3) 시작점 15, 중간점 16, 끝점, 15     => WOW~

=> 중간점 값은 시간이 지날수록 "최적화된 값"이므로 ! 떡 길이합이 떡 길이보다 크거나 같을 때만 중간점 값 기록!

 

 

 

 

• python

  # 떡 개수 n 와 필요한 떡 길이 m
  n, m = map(int, input().split())
  
  # 각 떡 개별 높이
  array = list(map(int, input().split()))
  
  # 이진탐색 위해 시작, 끝점
  start = 0
  end = max(array)
  
  # 이진탐색 시작
  result = 0
  while (start <= end) :
      total = 0
      mid = (start + end) // 2
      for x in array :
          if x > mid :
              total += x -mid
      # 부족
      if total < m :    # 왼
          end = mid - 1
      # 충분하니 덜 자르기
      else :    # 오른
          result = mid
          start = mid + 1
  
  print(result)

•  c++

#include <bits/stdc++.h>

using namespace std;

// 떡의 개수(N)와 요청한 떡의 길이(M)
int n, m;
// 각 떡의 개별 높이 정보 
vector<int> arr;

int main(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 이진 탐색을 위한 시작점과 끝점 설정
    int start = 0;
    int end = 1e9;
    // 이진 탐색 수행 (반복적) 
    int result = 0; 
    while (start <= end) {
        long long int total = 0;
        int mid = (start + end) / 2;
        for (int i = 0; i < n; i++) {
            // 잘랐을 때의 떡의 양 계산
            if (arr[i] > mid) total += arr[i] - mid; 
        }
        if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
            end = mid - 1;
        }
        else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
            result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록 
            start = mid + 1;
        }
    }
    cout << result << '\n';
}
© 2022 GitHub, Inc.

• java

  import java.util.*;
  
  public class Main {
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          
          // 떡의 개수(N)와 요청한 떡의 길이(M)
          int n = sc.nextInt();
          int m = sc.nextInt();
  
          // 각 떡의 개별 높이 정보 
          int[] arr = new int[n];
          for (int i = 0; i < n; i++) {
              arr[i] = sc.nextInt();
          }
  
          // 이진 탐색을 위한 시작점과 끝점 설정
          int start = 0;
          int end = (int) 1e9;
          // 이진 탐색 수행 (반복적)
          int result = 0; 
          while (start <= end) {
              long total = 0;
              int mid = (start + end) / 2;
              for (int i = 0; i < n; i++) {
                  // 잘랐을 때의 떡의 양 계산
                  if (arr[i] > mid) total += arr[i] - mid; 
              }
              if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
                  end = mid - 1;
              }
              else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
                  result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록 
                  start = mid + 1;
              }
          }
  
          System.out.println(result);
      }
  
  }

 

 

 

 

< 문제2 > 정렬된 배열에서 특정 수의 개수 구하기

: N 개의 원소 수열이 오름차순으로 정렬

: 수열에서 x 가 등장하는 횟수

: O(logN) 으로 하기 ( 선형 탐색은 시간 초과 )

: 데이터 정렬되어, 이진 탐색 가능

: 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이  계산

 

 

• python

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value) :
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)

    return right_index - left_index

# 데이터 개수 n, 찾고자 하는 값 x
n, x = map(int, input().split())
array = list(map(int, input().split()))

# [x, x] 범위 안에 있는 데이터 개수 계산
count = count_by_range(array, x, x)

if count == 0 :
    print(-1)
else :
    print(count)

• c++

#include <bits/stdc++.h>

using namespace std;

int countByRange(vector<int>& v, int leftValue, int rightValue) {
	vector<int>::iterator rightIndex = upper_bound(v.begin(), v.end(), rightValue);
    vector<int>::iterator leftIndex = lower_bound(v.begin(), v.end(), lowerValue);
    return rightIndex - leftIndex
}