1654 랜선 자르기 1. 문제유형 이분탐색, Binary Search 2. 자료구조 lans (list): 보유한 랜선의 길이를 저장하는 리스트 left, right (int): 랜선 최소길이, 최대길이 mid (int): 지정한 랜선 길이. left, right의 중간값 cnt (int): 잘라서 얻어낸 랜선 개수 3. 해결과정 최대 랜선 길이가 2^31-1이므로 이분탐색을 떠올렸다. 항상 n개의 랜선 개수를 만들 수 있으므로, 랜선 길이를 지정 후 n개가 되는지 테스트한다. 최대 범위가 2^31-1인 것을 깜빡해서 1차시도 때 오답으로 책정되었다. left, right를 지정하되 right의 범위는 2^31-1을 포함하도록 설정한다. mid 계산 후 cnt가 n을 만족하는 지 확인한다. cnt가 n..

1477 휴게소 세우기 1. 문제유형 이분탐색 2. 자료구조 distance (int): 도로 최대 길이 conv (list): 휴게소 위치를 담은 리스트 left, right (int): 휴게소가 없는 최대거리의 최소값(1), 최대값(distance-1) mid (int): 지정한 최대거리의 최소값. left, right의 중간값 current (int): 현재 위치를 저장할 변수 diff (int): 현재 위치 - 다음 휴게소 위치로 휴게소가 없는 거리 cnt (int): 설치한 휴게소 개수 3. 해결과정 ⭐ 놓친점) diff가 mid와 같은 경우 휴게소를 설치하지 않아야 한다. (따라서 diff-1을 mid로 나눈다.) ⭐ 아이디어) 휴게소가 없는 최대거리의 최소값을 지정하고, 휴게소를 설치를 완료..

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부터 적용할 ..