17393 다이나믹 롤러 1. 문제유형 Binary Search 2. 자료구조 ink (list): 잉크를 저장하는 리스트 vis (list): 점도를 저장하는 리스트 answer (list): 각 자리에서 최대 칠할 수 있는 타일 수를 저장하는 리스트 pos (int): 현재 타일 위치의 잉크값 l (int): 현재 위치의 바로 앞 타일 위치를 저장 r (int): 타일의 가장 끝 위치를 저장 mid (int): l,r의 중간값 res (int): 현재 위치에서 칠할 수 있는 최대 타일 위치 3. 해결과정 아이디어는 현재 위치 ink값보다 작은값들 중 최대값의 위치를 찾는다. 현재 위치 + 1 부터 ink값보다 작은 최대값 위치까지의 값을 카운트한다. 이 거리가 현재 위치에서부터 칠할 수 있는 타일 수..

징검다리 1. 문제유형 이분탐색 2. 자료구조 distance (int): 목적지 거리 rocks (list): 바위 위치를 저장한 리스트 left, right (int): 바위별 거리의 최소값, 최대값 mid (int): 정답으로 지정한 바위별거리. left, right의 중간값 current (int): 현재 바위 위치 diff (int): 현재 바위 위치를 기준으로 다음 바위까지의 거리 cnt (int): 제거한 바위 수 3. 해결과정 최대 범위가 10억이므로 이분탐색을 위해 rocks를 정렬 후 시작한다. 이분탐색을 지정하기 위해 최소, 최대거리를 지정한 후 mid를 계산한다. mid가 정답이이라고 가정한 뒤, 제거한 바위 수가 n과 같은지 판단한다. 바위를 하나씩 꺼내가며 diff를 계산하고, ..

12015 가장 긴 증가하는 부분 수열2 1. 문제유형 Binary Search, DP 2. 자료구조 lis (list): 최장 부분 순열을 저장하는 리스트 a (int): n개의 입력값을 저장하는 리스트 3. 해결과정 입력받은 값을 a에서 하나씩 꺼낸다. lis가 비어 있으면 꺼낸 값을 추가한다. 비어있지 않고, lis[-1] < num이면 꺼낸 값을 추가한다. 꺼낸 값이 lis의 마지막 값보다 작으면 이분탐색으로 들어갈 index를 찾고 덮어씌운다. 반복이 끝나면 lis의 길이를 출력한다. import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) a = list(map(int, input().split()..

1. 입국심사 1.1. 문제유형 이분탐색 1.2. 자료구조 times (list): 심판관별 심사시간 left, right (int): 최소 시간, 최대 시간 mid (int): 정답으로 지정한 left, right의 중간값 cnt (int): mid 시간안에 완료한 승객 수 1.3. 해결과정 구하고자 하는 것은 최소 시간이다. 이분탐색을 사용하여 정답 시간을 설정 후 지정한 시간안에 완료되는 지를 구한다. left, right 지정 후 left

2470 두 용액 1. 문제유형 Binary Search Two Pointer 2. 자료구조 l (int): 첫 번째 원소 인덱스 r (int): 마지막 원소 인덱스 flag (boolean): 탐색 여부를 결정하는 변수 3. 해결과정 시작하기 전, 정렬을 수행한다. 만약 첫 번째 값과 마지막 값이 모두 양수라면, 가장 작은 두 값을 출력한다. 만약 첫 번째 값과 마지막 값이 모두 음수라면, 가장 큰 두 값을 출력한다. 만약 첫 번째 값과 마지막 값의 부호가 다르다면, 탐색을 수행한다. 탐색과정은 flag and l < r동안 반복한다. sum의 절대값이 answer 값보다 작다면 answer에 sum을 저장하고, a,b = l,r를 저장한다. sum이 0보다 작다면 용해값을 키우기 위해 왼쪽값을 증가시..

2805 나무 자르기 1. 문제유형 Binary Search 2. 자료구조 left (int): 가장 작은 트리의 높이 right (int): 가장 높은 트리의 높이 mid (int): 트리의 중간 높이 3. 해결과정 ⭐ 실수한 점) 트리의 높이가 최대여야 나무를 가장 적게 가져간다. 따라서, 자른 나무 길이가 M보다 작을 경우 right의 크기를 감소시킨다. 반대로 자른 나무 길이가 M보다 클 경우, left 크기를 증가시켜 나무를 절약한다. ⭐ list(tree-mid for tree in trees if tree-mid>0)으로 계산한 뒤, sum 계산 시 시간 초과가 발생했다. 따라서 바로 sum(tree-mid for tree in trees if tree-mid>0)으로 계산해주니 바로 통과했..

4. 1300 K번째 수 4.1. 문제유형 Binary Search 4.2. 자료구조 left (int): 각 행의 최소값 인덱스 == 1 right (int): 각 행의 최대값 인덱스 == n mid (int): (left+right)//2 == 중간값으로 탐색해 나갈 값 4.3. 해결과정 핵심 아이디어는 행별로 mid값보다 작은 값의 개수를 세는 것이다. 각 행의 값은 i의 배수이며 작은 값들의 개수는 최대 n, 최소 mid // i이다. left

1072 게임 1. 문제유형 Binary Search 2. 자료구조 중요한 점은 y/x * 100과 같이 실수형으로 계산 후 int로 바꿔줄 시 정확하지 않을 수 있다. 따라서 실수형 계산이 아닌, y * 100//x처럼 정수형 계산으로 바꿔 승률을 계산해야 한다. z (int): 초기 승리한 게임 수 y/전체 게임 수 x * 100 target (int): 승리한 경기수를 이분탐색하며 계산한 승률 left (int): 더해나갈 승리한 횟수의 최소값 right (int): 더해나갈 승리한 횟수의 최대값 mid (int): (left+right)//2 == 중간값으로 실제 더할 승리한 횟수 3. 해결과정 승리한 게임 수를 찾는 게 핵심이며, 범위는 0부터 x(10 ** 9)까지이다. 따라서 1부터 적용할 ..

2110 공유기 설치 1. 문제유형 Binary Search 2. 자료구조 cnt (int): 공유기 개수 left (int): 최소 거리 == 1 right (int): 최대 거리 == (마지막 집 좌표 - 첫 번째 집 좌표) mid (int): 공유기 간 거리 == (left + right) // 2 wifi (int): 공유기가 설치된 집 좌표 3. 해결과정 집 좌표 최대 크기가 10억이므로, 순차탐색이 아닌 이분탐색을 떠올려볼 것 공유기 간 최대거리를 찾는 것이 목적이므로 이분탐색 활용할 것 left

1. 2343 기타 레슨 1.1. 문제유형 Binary Search1.2. 자료구조 cnt (int) : 블루레이 개수 file (int) : 레슨을 저장한 파일 크기 mid (int) : 블루레이 크기 left (int) : 가장 작은 블루레이 크기 right (int) : 가장 큰 블루레이 크기1.3. 해결과정 가장 작은 블루레이 크기는 max(lesson), 최대 크기는 sum(lesson)이다. 주어진 m개의 블루레이에 강의를 저장하되, 블루레이 크기는 작을수록 좋다. 따라서 블루레이의 크기를 찾는 이분탐색 문제로 해결할 수 있다. left는 max(lesson), right는 sum(lesson)로 설정한다. left m: left = mid+1 else: answer = mid right = ..