2020 동계 모각코 6주차

오늘의 계획

대표적인 관계형 DB인 MYSQL 강의 듣기
- 섹션 5 - MySQL 더 배워보기
이분탐색 알고리즘 공부 및 문제 풀이
- 백준 문제 풀이

오늘의 회고

인프런 DataBase 강의 수강
- RENAME 명령어로 topic이라는 TABLE의 이름을 topic_backup으로 변경하였다.
- table에서 중복되어 있는 author와 profile 때문에 기존의 topic에 담겨있던 내용을 topic과 author이라는 두 table로 분리하였다.
- topic table의 author_id값과 author table의 id값을 참고하여 두 table을 합침
이분탐색 알고리즘 문제 : 랜선 자르기 (SILVER 3)
- 이분탐색 알고리즘 : 이분탐색(이진탐색) 알고리즘은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘을 의미한다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값인 X와 비교해 X가 중간 값보다 작다면 중간 값을 기준으로 좌측의 데이터를 대상으로, X가 중간값보다 크다면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교하며 위의 과정을 반복한다.
- 해결 방법 :
  - 이분탐색 알고리즘을 활용하여 left와 right의 중간값으로 랜선을 잘라 그 개수를 더해 비교하였다. 하지만 처음에는 재귀함수로 구현하였는데 계속 시간초과 문제가 발생해서 while문으로 바꿔주었다.
  - K개의 랜선 중 가장 큰 값을 찾아 그 값을 right로 지정하였고, 존재할 수 있는 가장 작은 길이인 1을 left로 지정하였다.
  - right와 left의 중간 값인 mid로 각 K개의 랜선들을 나누어 count에 더해주었고, 이 값을 N과 비교하여 N보다 작다면 랜선의 개수가 모자란 것이므로 right를 mid - 1로, N보다 크거나 같다면 랜선의 개수가 충분한 것이므로 answer vector에 push해주고 left를 mid - 1로 저장하였다. left가 right보다 커지면 반복문은 종료되고,
  - answer vector에 저장된 예비 정답들 중 max_element 함수로 최대값을 찾아내어 출력하였다.
- 코드
```
```c++
  #include <iostream>
  #include <vector>
  #include <algorithm>
  using namespace std;
  vector<long> answer;
  vector<long> wire;
  long K, N; //K<=N
  
  void solution(long long left, long long right) {
      //left > right가 되면 종료
      while(left <= right){
          int count = 0; //각 랜선을 잘라 N개 이상이 되는지 비교
          long long mid = (left + right) / 2;
          //이분탐색으로 중간 값으로 자름
          for (int i = 0; i < wire.size(); i++) {
              count += (wire[i] / mid);
          }
  
          if (count < N) { //랜선의 개수가 모자란 경우
              right = mid - 1;
          }
          else { //랜선의 개수가 충분한 경우 (N 이상)
              answer.push_back(mid); //예비 정답 vector에 push
              left = mid + 1;
          }
      }
  }
  
  int main(void) {
  
      cin >> K >> N;
  
      for (int i = 0; i < K; i++) {
          int input;
          cin >> input;
          wire.push_back(input);
      }
      long long right = *max_element(wire.begin(), wire.end()); //최대 값을 우측 값으로
      long long left = 1; //최소 값인 1을 좌측 값으로
  
      solution(left, right);
  
      //예비 정답이 담긴 answer vector에서 가장 큰 값을 찾아 출력
      cout << *max_element(answer.begin(), answer.end());
  }
  
```
```