210420 결정 알고리즘(Decision algorithm)을 활용한 문제풀이
결정 알고리즘은 이분검색을 기반으로 한다.
알고리즘 문제에서 주어진 조건에서의 최대값 혹은 최소값을 구하는 문제 중에 몇 몇 문제는 결정 알고리즘(Decision algorithm)을 활용해서 풀이해야 한다.
결정 알고리즘은 이분 검색을 기반으로 하는 문제로, 전체 데이터를 순회하면 시간 복잡도 O(N)을 갖지만 이분 검색으로 데이터를 검색하면 O(logN)만큼의 시간 복잡도를 갖는다.
예시문제
길이가 N인 숫자 리스트가 있다고 가정했을때, 총 T 개의 그룹으로 리스트를 나눠야 한다.
T개의 그룹으로 리스트를 나눴을때 한 그룹당 최소 얼마의 숫자합이여야 하는지 구하시오.