1주차 정리

• 기간: 10.28(월) ~ 10.31(목)
• 알고리즘 종류: 이분탐색

  • 최대 또는 최소 $k$ 또는 $k$ 값 찾기
  • 이분 탐색의 대상 및 조건 설정: 최대 또는 최소 $k$ 값을 찾을 때, 부등호 방향 (예: >=, <=)을 명확히 설정하자.
  • C++의 경우, 연산 중간 과정에서 오버플로우가 발생할 수 있으므로 자료형 선택에 주의가 필요

[백준] 예산 - 2512

• [백준] 예산 - 2512
• Silver II
• C++ 풀이

문제해설

접근법: 이분 탐색

대상: 상한액 (vs 전체 국가 예산)

#include <bits/stdc++.h>
using namespace std;

int N;
long long M;
int arr[10001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    memset(arr, 0, sizeof(arr));

    cin >> N;
    for (int i = 0; i < N; i++) { cin >> arr[i]; }
    cin >> M;

    int st = 0, ed = *max_element(arr, arr + N), mid;
    long long answer = M;
    while (st <= ed){
        mid = (st + ed) / 2;
        long long sumN = 0;
        for (int i = 0; i < N; i++){
            sumN += (long long)min(arr[i], mid);
        }
        if (sumN <= M){
            answer = mid;
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    cout << answer << "\n";
    return 0;
}

이번주 회고

나는 알고리즘 문제를 편식하는 경향이 있었고, 특히 이분탐색은 피했던 유형 중 하나였다.
이번에 이분탐색 문제들을 집중적으로 다뤄보며, 이 유형이 생각보다 효율적이고 가성비가 좋다는 점을 알게 되었다.

이분탐색은 대상만 명확히 파악하면, 1) 코드를 빠르게 작성할 수 있고, 2) 빈출 유형이며, 3) 기출도 매번 유사하게 출제 된다는 장점이 있다.

과거 코딩테스트에서도 이분탐색 문제를 접한 적이 있었지만, 당시에는 이 유형인지 자체를 인식하지 못했던 것 같다. 오늘 푼 문제 역시 최근 코딩 테스트에서 봤던 통신사 모 기업의 문제와 비슷했는데, 이번에는 20분 만에 해결할 수 있었다.
기업에서 요구하는 코딩 테스트는 거창한 기술력을 요구하는 것이 아니라, 성실히 준비한 흔적을 보는 것이라는 다시금 깨달았다. 앞으로는 이러한 후회를 반복하지 않기 위해 다양한 유형을 두루 연습하며 체계적으로 대비해야겠다는 다짐을 하게 되었다.