[99클럽 코테 스터디] 99클럽 코테 스터디 11일차 TIL + 이분탐색

Posted by , April 14, 2025
99클럽코딩테스트준비개발자취업항해99TIL
Series of99클럽 코테 스터디

99클럽 코테 스터디

1. 오늘의 학습 키워드

2. 공부한 내용 본인의 언어로 정리하기

  • 시도1
    • 소스 코드
    import java.io.*;
    public class Main {
        public static void main(String[] args) throws IOException {
            // 입력
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] tmpArr = br.readLine().split(" ");
    
            int m = Integer.parseInt(tmpArr[0]); // 조카 수
            int n = Integer.parseInt(tmpArr[1]); // 과자 수
    
            long[] inputArr = new long[n];
            long maxLen = 0;
    
            String[] tpmArr2 = br.readLine().split(" ");
            for (int i=0; i<n; i++) {
                inputArr[i] = Long.parseLong(tpmArr2[i]);
                maxLen = Math.max(maxLen, inputArr[i]);
            }
    
            long left = 1;        // 시작점
            long right = maxLen;  // 끝점
            long result = 0;
    
            // 길이를 1부터 가장 긴 과자 길이까지 이진 탐색 시작
            // "숫자 범위"에서 최적의 값을 찾는 문제는 → 이진 탐색을 숫자 범위에 해야 한다.(예: 나무 자르기, 랜선 자르기, 과자 나눠주기 등)
            while (left <= right) {
                long mid = (left + right) / 2;
                long count = 0;
                // 각 과자를 mid 길이로 잘랐을 때 몇 개가 나오는지 합산
                for (long num : inputArr) {
                    count += num / mid;
                }
                // 줄 수 있는 과자 수가 조카 수 이상이면 더 길게 자를 수도 있음
                if (count >= m) {
                    result = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // 출력
            System.out.println(result);
        }
    }
  • 이분 탐색
    • 정렬된 배열이나 리스트에서 원하는 값을 빠르게 찾는 알고리즘를 말한다.
    • 반드시 오름차순(또는 내림차순)으로 정렬되어 있어야 한다.
    • 동작 방식
      • 배열의 중간값을 찾는다.
      • 찾는 값이 중간값보다 작으면 왼쪽, 크면 오른쪽으로 탐색 범위를 줄인다.
      • 범위가 좁아질 때까지 반복한다.
    • 사용되는 상황
      • 효율적으로 검색이 필요할 때
      • 예: 값의 존재 여부, 최댓값/최솟값 구하기, 조건을 만족하는 값 찾기, 나무 자르기, 랜선 자르기, 과자 나눠주기

3. 오늘의 회고

  • 문제 상황과 시도

문제를 보고 어떤 알고리즘을 사용해야 할지 바로 떠오르지 않았다. 완전 탐색으로 접근하면 시간 초과가 날 것 같았고, DFS나 BFS 알고리즘도 적용되지 않을 것 같았다.

  • 해결 과정

힌트를 통해 이분탐색을 사용해야 한다는 것을 알게 되었지만 이 알고리즘이 생소해서 구현하는 데 어려움이 있었다.

  • 배운 점

이분탐색은 처음 접했을 때 구현이 어렵지만 문제를 풀고 나니 그 효율성을 잘 이해할 수 있었다. 알고리즘을 배우고 익히는 과정에서 반복적인 연습의 중요성을 다시 한 번 느꼈다.