8983 사냥꾼 1. 문제유형 이분탐색, 정렬 2. 자료구조 m (int): 사대의 수 n (int): 동물의 수 l (int): 사대 사정거리 gun (list): 사대 좌표를 담은 리스트 animal (list): 동물 좌표를 담은 리스트 cnt (int): 잡은 동물의 수 s (int): 해당 동물을 잡을 수 있는 최소 사대 좌표 e (int): 해당 동물을 잡을 수 있는 최대 사대 좌표 left, right(int): 사대 좌표의 최소값(0), 최대값(m-1) 인덱스 mid (int): 동물을 잡을 수 있는 사대 좌표값 (left+right)//2 3. 해결과정 ⭐ 사대 거리를 고정하고 가능한 동물 수를 구하려고 하면 시간 복잡도가 높아진다. (n^2) ⭐ 따라서 동물을 고정하고, 잡을 수 있는 ..

11977 Angry Cows 1. 문제유형 이분탐색, 정렬, 브루트포스 2. 자료구조 n (int): 건초의 수 bay (list): 건초의 위치를 담은 리스트 cur (int): 현재 건초의 위치 인덱스 rad (int): 폭발 사정거리 l (int): 옮겨 붙을 왼쪽 건초 좌표 인덱스 r (int): 옮겨 붙을 오른쪽 건초 좌표 인덱스 cnt (int): 폭발시켜 태운 건초의 최대값 3. 해결과정 ⭐왼쪽으로 옮겨 붙는 경우와 오른쪽으로 옮겨 붙은 경우를 나누어 구했다. ⭐왼쪽으로 옮겨 붙을 때는 터뜨린 가장 왼쪽 건초 index까지 count한 후 rad를 증가시킨다. ⭐오른쪽으로 옮겨 붙을 때 역시, 터뜨린 가장 오른쪽 건초 index까지 count한 후 rad를 증가시킨다. 0번째 건초부터 n-..

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)으로 계산해주니 바로 통과했..