알고리즘 - 이진탐색 문제풀이

문제)

// Practice5
// 정수형 배열 nums 와 정수 m 이 주어졌다.
// nums 에는 양의 정수 값들이 들어 있고, m 은 배열을 부분 배열로 분리할 수 있는 수이다.
// nums 배열을 m 개의 부분 배열로 분리할 때,
// 각 부분 배열의 합중 가장 큰 값이 최소가 되도록 분리했을 때의 합을 출력하세요.

// 입출력 예시
// nums: 7, 2, 5, 10, 8
// m: 2
// 출력: 18

// nums: 1, 2, 3, 4, 5
// m: 2
// 출력: 9

 

 

구현 코드)

public class Practice5 {
    public static int solution(int[] nums, int m) {
        int left = 0;
        int right = 0;

        for (int num : nums) {
            left = Math.max(num, left);
            right += num;
        }

        if (m == 1) {
            return right;
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 1;
            int total = 0;

            for (int num : nums) {
                total += num;
                if (total > mid) {
                    total = num;
                    cnt++;
                }
            }

            if (cnt <= m) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {7, 2, 5, 10, 8};
        System.out.println(solution(nums, 2));  // 18

        nums = new int[] {1, 2, 3, 4, 5};
        System.out.println(solution(nums, 2));  // 9

        nums = new int[] {1, 4, 4};
        System.out.println(solution(nums, 3));  // 4
    }
}

 

 

• 초기 설정:
  • left는 배열의 원소 중 가장 큰 값으로 초기화
    • 이는 최소한의 가능한 최대 부분 배열 합입
    • 각 부분 배열은 적어도 하나의 원소를 포함해야 하므로, 그 중 가장 큰 값이 최솟값
  • right는 배열의 모든 원소의 합으로 초기화
    • 이는 하나의 부분 배열로 모두 합친 경우로, 가능한 최대 부분 배열 합
• 이진 탐색:
  • 이진 탐색을 통해 left와 right 사이의 중간값인 mid를 구함
    • 이 mid 값을 기준으로 배열을 m개의 부분 배열로 나눌 수 있는지를 검사
• 그리디 알고리즘으로 배열 나누기:
  • 배열을 순차적으로 탐색하면서, 현재 부분 배열의 합에 값을 더해 나감.
    • 이 합이 mid를 초과할 경우, 새로운 부분 배열을 시작해야 함.
    • 이때 부분 배열의 개수를 cnt로 증가
  • 만약 cnt가 m보다 작거나 같다면, 현재 mid 값으로도 m개의 부분 배열로 나눌 수 있다는 의미
    • 이 경우 더 작은 mid 값을 탐색하기 위해 right를 mid - 1로 줄임
  • 반대로 cnt가 m보다 크다면, 현재 mid 값으로는 m개로 나누는 것이 불가능하다는 의미
    • 더 큰 mid 값을 탐색하기 위해 left를 mid + 1로 늘림
•   결과 반환:
  • 최종적으로 이진 탐색이 종료될 때 left가 가리키는 값이 가장 적합한 값이 됩니다. 이는 각 부분 배열의 합 중 가장 큰 값이 최소가 되는 경우의 그 값

 

 

출력 결과)

18
9
4