졍's 기술 블로그

1. Framework

: Software 분야에서 Application을 개발에 빈번히 쓰여지는 범용 기능을 한꺼번에 제공해 Application의 토대로서 기능하는 Software이다. Application의 아웃라인으로 개발에 Framework를 이용하면 독자적으로 필요로하는 부분만 개발하면 되기 때문에 개발 효율의 향상을 기대할 수 있다.

e.g., Spring, Django, node.js 등

1.1. 특징

• 공통적인 개발 환경을 제공한다. (개발 편의성)
• 개발할 수 있는 범위가 정해져있다.
• Application 제어의 역전이 발생한다.

2. Library

: 개발자가 사용할 수 있는 API들을 종류나 목적에 따라 나누어 정의한 API 묶음으로 재사용 가능한 Code의 집합이다. Library는 System에 기본적으로 설치되어있는 기본 Library와 제조사나 외부 메이커에 의해 만들어지는 확장 Library로 나뉜다.

e.g.,

import random # random Library를 사용하겠다.
random_num = random.randrange(1, 7) # random Library에 포함되어 있는 함수를 이용해 값 반환

2.1. 특징

• 개발에 필요한 것들을 모아둔 일종의 저장소이다.
• 필요할 때 호출해서 사용한다.
• Application의 흐름을 제어한다
  ☞ Framework와 반대

3. API(Application Programming Interface)

: 응용 프로그램에서 사용할 수 있도록 운영체제나 다른 프로그램이 제공하는 기능을 제어할 수 있게 만든 Interface이다.

3.1. 특징

• 응용 프로그램을 다른 운영체제나 Program과 연결해주는 다리 역할을 한다.
• 직접 구현하는 것이 아닌 제어를 담당한다.
• API를 조합해 원하는 Program을 만들 수 있다.

4. 비유를 통한 Framework, Library, API의 이해

집을 지을 때 아래의 조건이 만족되어야 한다고 가정해보자.

1. 3개의 방, 1개의 화장실이 존재해야 한다.
2. 에어컨이 존재해야 한다.
3. 조명, 가전제품 등을 제어할 수 있는 리모컨이 존재해야 한다.

• 1번 조건 : 맨땅에 헤딩하기보다는 평면도를 이용해 여러 사람이 협업하면 효율성이 높아질 것이다.
  ☞ 평면도 = Framework
• 2번 조건 : 에어컨을 실제로 만들기보다는 기존에 만들어져 있는 에어컨을 구매해 가져다 놓으면 불필요한 시간과 노력을 줄일 수 있을 것이다.
  ☞ 기존 제품 = 외부 Library
• 3번 조건 : 리모컨을 이용해 제품을 제어한다면 리모컨 없이 제어할 때보다 더 쉽게 제어할 수 있을 것이다.
  ☞ 리모컨 = API

5. Library와 Framework의 공통점과 차이점

[참고]

https://youtu.be/We8JKbNQeLo

https://youtu.be/_j4u4ftWwhQ

수열 걷기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 구현, 두 포인터

문제

길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.

아래는 두 수열과 교차점은 굵게 나타낸 것이다.

수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62

수열 2 = 1 4 7 11 14 25 44 47 55 57 100

이 두 수열은 다음과 같이 걸을 수 있다.

1. 두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.
2. 교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈아탈지 결정할 수 있다.

방문한 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 위의 예에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62와 같이 걷는다면 합이 450으로 최대가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 줄로 이루어져 있다.

각 줄의 첫 번째 수는 수열의 길이이다. 그 다음에는 수열의 원소가 순서대로 주어진다. 수열의 길이는 1이상이고, 10,000을 넘지 않는다. 수열에 들어있는 모든 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 얻을 수 있는 최대 합을 출력한다.

예제 입출력

Algorithm

이진 탐색 - bisect
1. bisect를 이용해 수열1과 수열2의 같은 값 찾기
2. 같은 수를 찾으면 각 수열에서 해당 숫자 이전까지의 합 구하기
3. answer에 각 수열의 합 중 최댓값 저장

Code

import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

while True:
    # 입력
    sequence1 = list(map(int, input().split()))
    # 0이 하나 주어지면 break
    if sum(sequence1) == 0:
        break
    seq1_len = sequence1[0]
    sequence1 = sequence1[1:]
    sequence2 = list(map(int, input().split()))
    seq2_len = sequence2[0]
    sequence2 = sequence2[1:]

    answer = 0
    index1 = 0 # 수열 1의 동일한 숫자의 index
    index2 = 0 # 수열 2의 동일한 숫자의 index
    for num in sequence1:
        # 동일한 숫자가 있으면
        if bisect_right(sequence2, num) - bisect_left(sequence2, num) > 0:
            # 첫 번째 수열의 해당 숫자까지의 합
            sum_seq1 = sum(sequence1[index1:bisect_right(sequence1, num)])
            # 두 번째 수열의 해당 숫자까지의 합
            sum_seq2 = sum(sequence2[index2:bisect_right(sequence2, num)])
            
            # 각 수열의 누적합 중 큰 값을 answer에 누적합
            answer += max(sum_seq1, sum_seq2)
            
            # 각 수열의 inex 갱신
            index1 = bisect_right(sequence1, num)
            index2 = bisect_right(sequence2, num)

    # 마지막 길의 최댓값 구해 answer에 추가
    answer += max(sum(sequence1[index1:]), sum(sequence2[index2:]))
    print(answer)

메모리: 33948 KB
시간: 100 ms

1. Transport Layer(전송 계층)

: End Point 간 신뢰성있는 Data 전송을 담당하는 계층

신뢰성 : Data의 순차적, 안정적인 전달 보장
전송 : 목적지 Port 번호에 해당하는 Process에 Data 전달

1.2. Transport Layer의 중요성

만약, 전송 계층이 없다면 ?

• Data의 순차 전송이 원활히 이루어지지 않음
  e.g., 송신자가 1 2 3의 순서로 Data를 전송했을 때 수신자는 Data 수신 시 2 3 1 등의 순서로 전송받을 수 있다.
• Flow 문제(흐름 문제) 발생
  Flow 문제의 원인 : 송·수신자 간의 Data 처리 속도의 차이
  e.g., 수신자가 처리할 수 있는 Data의 양을 초과하는 경우 그 이후에 송신되는 Data의 경우 누락될 수 있다.
• Congestion 문제(혼잡 문제) 발생
  Congestion 문제의 원인 : Network(e.g. Router)의 Data 처리 속도
  e.g., 송신자가 계속 Data를 저송하더라도 Network가 혼잡해 수신자에게 제대로 전달되지 않을 수 있다.

∴ Data의 손실이 발생할 수 있다.

2. TCP(Transmission Control Protocol)

: 신뢰성있는 Data 통신을 가능하게 해주는 Protocol

• Data 전송 전 Connection 연결이 필요하다. (3-Way Handshake : 양방향 통신)
• Data의 순차 전송을 보장한다.
• Flow Control (흐름 제어)
• Congestion Control (혼잡 제어)
• Error Detection (오류 감지)
  ☞ Checksum 이용

2.1. Segment

: TCP의 PDU(Protocol Data Unit, 프로토콜 데이터 단위)

Application 계층에서 Data를 전송하면 TCP Protocol 안에서 내부적으로 Data를 잘라 TCP Header와 Data를 결합한다.

2.2. TCP Header의 구조

• Source Port : 송신자 Port 번호
• Destination Port : 수신자 Port 번호
• Sequence Number, Acknowledgment Number : 순차 전송 담당
• Flag Field : TCP 연결 제어 및 Data 관리
• Checksum : Error 검출

2.3. 3-Way Handshake (Connection 연결)

   ① Client가 SYN 비트를 1로 설정해 Server에 Packet 송신

   ② Server가 SYN, ACK 비트를 1로 설정해 Client에 Packet 송신

       ☞ ACK 비트로 Data를 받았음을 알림

   ③ Client가 ACK 비트를 1로 설정해 Server에 Packet 송신

   ④ 열결 완료 후 Data 송수신

2.4. Data 전송 방식

   ① Client가 Server에 Packet 송신

   ② Server가 ACK 비트를 1로 설정해 Client에게 Packet 송신

   ③ Client가 ACK를 받지 못하면 Packet 재전송

       ☞ 신뢰성 있는 통신 보장

2.5. 4-Way Handshake (Connection Close)

   ① Data를 전부 전송한 Client가 FIN 비트를 1로 설정해 Server에 Packet 송신

   ② Server가 ACK 비트를 1로 설정해 Client에 Packet 송신

   ③ Server에서 남은 패킷 송신 (Client는 일정 시간 대기)

   ④ Server가 FIN 비트를 1로 설정해 Client에 Packet 송신

   ⑤ Client가 ACK 비트를 1로 설정해 Server에 Packet 송신

2.6. 문제점

• 전송의 신뢰성은 보장하지만 매번 Connection을 연결해 시간 손실이 발생한다. (3-Way Handshake)
• Packet을 조금만 손실해도 재전송한다.

3. UDP(User Datagram Protocol)

: TCP에 비해 신뢰성은 떨어지지만 전송 속도가 일반적으로 빠른 Protocol

• Connectionless (3-Way HandShake 과정이 없다 : 단방향 통신)
• 순차 전송, 흐름 제어, 혼잡 제어 기능이 없다.
• Error Detection
  ☞ Checksum 이용
• 비교적 Data의 신뢰성이 중요하지 않을 때 사용된다.
  e.g., 영상 스트리밍

3.1. User Datagram

: UDP의 PDU(Protocol Data Unit, 프로토콜 데이터 단위)

• Application 계층에서 Data가 전송되면 Data에 UDP Header를 추가해 만들어진다.
  ☞ Segment는 Data를 쪼갰으나 Datagram은 Data를 쪼개지 않는다.

3.2. UDP Header

• Source Port : 송신자 Port 번호
• Destination Port : 수신자 Port 번호
• Checksum : Error 검출

3.3. UDP의 Data 전송 방식

   ① Client가 Packet 송신

[참고]

https://youtu.be/ikDVGYp5dhg

https://diy-multitab.tistory.com/27

보석 상자

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ \(10^9\), 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, \(10^9\)]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

출력

첫째 줄에 질투심의 최솟값을 출력한다.

예제 입출력

Algorithm

이진 탐색 - 반복
mid : 한 사람이 최대로 받을 수 있는 보석 개수 (질투심)
for문 안에서의 조건
➝  보석의 개수 // mid : 보석을 받는 학생 수
➝  보석의 개수 % mid : 남는 보석 수
➝  보석을 mid로 나눴을 때 나머지가 없으면 학생수 = 보석의 개수 // mid
➝  보석을 mid로 나눴을 때 나머지가 있으면 학생수 = 보석의 개수 // mid + 1
mid 값 갱신의 조건
➝ 보석을 받은 학생 수가 N명보다 많으면 나누어주는 보석의 개수 증가
➝ 보석을 받은 학생 수가 N명보다 적으면 나누어주는 보석의 개수 최솟값 갱신

Code

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
gems = []
for _ in range(M):
    gems.append(int(input()))

# start, end 초기화
start = 1
end = sum(gems)

# 이진 탐색
answer = 0
while start <= end:
    
    mid = (start + end) // 2

    # mid가 0이면 break
    if mid == 0:
        break
    
    num_student = 0
    for num_gem in gems:
        
        if num_gem % mid > 0:
            num_student += num_gem // mid + 1
        else:
            num_student += num_gem // mid

    # 보석을 받은 학생의 수가 N명 보다 많으면 mid값 증가시켜 재탐색
    if num_student > N:
        start = mid + 1
    else: # 보석을 받은 학생 수가 N명보다 적으면 mid값 감소시켜 재탐색
        end = mid - 1
        answer = mid
        
print(answer)

메모리: 42616 KB
시간: 3300 ms

용돈 관리

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입출력

Algorithm

이진 탐색 - 반복
mid : 한 번에 뺄 수 있는 금액 (K)
for문 안에서의 조건
➝ 잔고가 오늘 예산보다 적으면 인출
mid 값 갱신의 조건
➝ 출금 횟수가 M보다 커지거나 mid값이 예산의 최댓값보다 작은 경우 mid를 키워서 재탐색
➝ 출금횟수가 M보다 작거나 같으면 mid 줄여서 재탐색 (최솟값 갱신)

Code

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
budget = []
for _ in range(N):
    budget.append(int(input()))

# start, end 초기화
start = min(budget)
end = sum(budget)

# 이진 탐색
answer = 0
while start <= end:
    
    mid = (start + end) // 2
    
    balance = 0
    count = 0
    for today in budget:
        
        # 오늘 예산보다 잔고가 부족하면 인출
        if balance < today:
            balance = mid
            count += 1
        
        balance -= today
    
    
    # 인출 횟수가 M보다 많거나 mid가 예산의 최댓값보다 작으면 mid값 증가시켜 다시 탐색
    if count > M or mid < max(budget):
        start = mid + 1
    else: # 인출 횟수가 M과 같거나 M보다 적으면 mid값 감소시켜 다시 탐색
        end = mid - 1
        answer = mid

print(answer)

메모리: 33688 KB
시간: 540 ms

랜선 자르기

티어 : Silver 3
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입출력

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

Algorithm

1. 이진 탐색 - 재귀 이용
2. 랜선의 길이를 mid로 보고 mid가 가장 클 때의 랜선의 길이 출력

Code

import sys
sys.stdin.readline

def binary_search(start, end):
    global answer
    
    # 찾는 값이 없으면 None Return
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    # mid가 0이 되면 None Return
    if mid == 0:
        return None
    
    # mid의 길이로 몇 개의 랜선을 만들 수 있는지 확인
    total = 0
    for i in length:
        total += i // mid
    
    # mid의 길이로 잘랐을 때 N개의 랜선을 만들 수 있으면 최댓값 찾기
    if total >= N:
        answer = mid
        return binary_search(mid + 1, end)
    else: # mid의 길이로 잘랐을 때 N개의 랜선을 만들 수 없으면 mid의 값을 줄여 다시 탐색
        return binary_search(start, mid - 1)

# 입력
K, N = map(int, input().split())
length = []
for _ in range(K):
    length.append(int(input()))

answer = 0
binary_search(1, max(length))
print(answer)

메모리: 30860 KB
시간: 460 ms

먹을 것인가 먹힐 것인가

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입출력

Algorithm

1. bisect_left 이용
2. bisect_left()의 x값을 본인으로 했을 때의 반환값이 현재 index의 값이 먹을 수 있는 먹이 수
3. 반환되는 값 누적 합해 출력

Code

import sys
from bisect import bisect_left

input = sys.stdin.readline

# 입력
T = int(input())
for _ in range(T):
    _, _ = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # B 정렬
    B.sort()
    
    answer = 0
    for i in A:
        # B List에서 A의 보다 작은 원소의 개수 누적합
        answer += bisect_left(B, i)
    print(answer)

메모리: 353116 KB
시간: 172 ms

예산

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

예제 입출력

Algorithm

1. 이진탐색 - 재귀 이용
2. mid를 상한으로 했을 때 요청되는 예산이 합이 총 예산보다 작으면 answer를 최댓값으로 갱신

Code

import sys
input = sys.stdin.readline

# 이진탐색 함수
def binary_search(start, end):
    global answer
    
    # 찾는 값이 없으면 None 반환
    if start > end:
        return None

    mid = (start + end) // 2
    
    # mid index의 값으로 상한값을 정했을 때 전체 예산 계산
    total = 0
    for i in request:
        # 요청 금액이 상한값보다 크면 상한값으로 요청
        if mid < i:
            total += mid
        # 그 외의 상황은 요청 금액 그대로 요청
        else:
            total += i
    
    # mid index의 값으로 상한값을 정했을 때 전체 예산 넘어가면 상한값을 낮춰야함
    if total > budget:
        return binary_search(start, mid - 1)
    
    else: # 그 외의 상황에서는 상한값의 최댓값 찾기
        if mid > answer:
            answer = mid
            return binary_search(mid + 1, end)

# 입력
_ = int(input())
request = list(map(int, input().split()))
budget = int(input())

answer = 0
binary_search(0, max(request))
print(answer)

메모리: 30864 KB
시간: 76 ms