이진탐색

*이 글은 2022년 1월~2월 노션으로 진행한 알고리즘 스터디를 옮긴 글입니다. 나동빈 저자 이것이 취업을 위한 코딩테스트다를 사용해 학습했습니다.

220214 이진탐색 개념 정리

• 필기
  
  

220215 실전문제

• 부품찾기
  • 풀이
    • 이진탐색 적용하면 바로 풀 수 있음
    • 풀다가 설마하고 찾아봤는데 이진탐색도 stl이 있음... 코드 오류로 고생했던 15분이 날아간 느낌-_-
    • #include헤더 추가하고 binary_search(시작지점,끝지점,찾으려는값) 으로 사용 가능한 bool타입 함수임.
  • 코드

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector<int> datas;
    
    int main() {
    	int n, m, a, b;
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		cin >> a;
    		datas.push_back(a);
    	}
    	sort(datas.begin(), datas.end());
    	cin >> m;
    	for (int i = 0; i < m; i++) {
    		cin >> b;
    
    		*if (binary_search(datas.begin(), datas.end(), b)) cout << "yes" << endl;
    		else cout << "no" << endl;
    	}*
    	return 0;
    }

• 떡볶이 떡 만들기
  • 풀이
    • n,m떡 길이를 모두 입력받고 vector에 저장함
    • h를 1로 설정하여 떡길이-h의 합계가 m과 같거나 클때까지 h를 1씩 더함
    • 근데 값이 이상하게 나옴. 17이 나옴... 어디서 잘못된건지 모르겠음
    • 생각해보니 입력값이 커서 내 방식대로 구현했어도 시간초과일듯
    • 그럼 이진탐색으로 구현해야 되는데 그건 어떻게?
    • 2트는 저자 깃허브에 있는 코드 긁어와서 분석함
  • 코드(1트)

    #include<iostream>
    #include<vector>
    using namespace std;
    
    vector<int>datas;
    int main() {
    	int n, m, a;
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) {
    		cin >> a;
    		datas.push_back(a);
    	}
    	int h = 1;
    	int answer;
    	do {
    		answer = 0;
    		for (int i = 0; i < n; i++) {
    			int k=datas[i] - h;
    			if (k <= 0)k = 0;
    			answer += k;
    		}
    		h++;
    	} while (answer >= m);
    	cout << h;
    	return 0;
    }

  • 코드(2트) 풀이참조

    • 이건 h값을 이진탐색으로 찾는 방법. 이진탐색 파트인데 하루 지났다고 어떤 문제인지 추론하는 것도 실패함 ㅋ_키;

    • 혼자서 꼭 다시풀기. 이진탐색 코드에 익숙해지기.

      using namespace std;
      #include<vector>
      #include<iostream>
      
      // 떡의 개수(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';
      }