혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 이분 탐색을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 정렬한 뒤, 최대값에서 빼가면서 총 예산(M)을 맞추는 것은 각 예산 값들이 100,000 이하인 것을 감안하면 시간 제한(1초)를 맞출 수 없다. 따라서 이분 탐색을 통해 시간 복잡도를 log로 변환하여 작업을 줄이도록 한다. 예산의 값 중 최대값을 찾는다. 최소값과 최대값의 평균값(mid)을 구해 각 예산에 상한선을 적용한 뒤, 총 예산과 비교한다. 총 예산보다 작으면, mid값을 저장하고 mid값을 최소값으로 설정한 뒤 4번 작업 반복. 총 예산보다 크면, mid값을 최대값으로 설정한 뒤 4번 작업 반복. 최대값과 최소값이 같으면 반복을 종료하고, 저장된 mid값 중 가장 큰 값을..

안녕하세요 GODZ입니다. 오늘은 이분 탐색과 투 포인터를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 N개의 수를 하나씩 입력 받으면서 합 sum을 구한다. sum >= S 일 때, 길이 len을 저장하고 0번 인덱스부터 S보다 작아질 때까지 sum에서 뺀다. sum = S 일 때, 2번 작업 반복. 모든 수를 다 입력 받았으면 저장한 길이 len 중 최소값을 찾는다. 만약 저장한 길이 len이 존재하지 않는다면 0을 출력한다. 4. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..