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. 입국심사 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부터 적용할 ..