정신 차리고 살자

문제 (https://www.acmicpc.net/problem/3020) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제를 읽고 고민을 하다가.. 예전에 푼 문제에서 lower_bound와 upper_bound를 사용했던 게 생각이 났다. 구현을 해봤지만 시간 초과가 발생했고 구글링으로 약간의 힌트를 얻은 후 구현했다. 석순과 종유석을 각각 입력받고 정렬한다. 정렬 후, 1부터 h까지 반복하며 각 높이일 때 몇 개의 장애물을 파괴하는지를 구한다. 이때 lower_bound를 사용하는 것이다. 장애물의 개수..

문제 (https://www.acmicpc.net/problem/1477) 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분 탐색 문제이다. vector에 휴게소의 시작점과 끝점(0, l), 입력받은 위치들을 넣어주고 정렬한다. 1 ≤ 휴게소의 위치 ≤ l - 1이므로 start = 1, end = l - 1로 설정했다. 휴게소 사이의 거리인 mid를 구하고 기존 휴게소 사이에 몇 개의 휴게소를 설치할 수 있는지 계산한다. 이때, dist % mid 값이 0이라면 휴게소 위치가 겹치는 것이므로 개수를 하나 빼야 함! 예를 들어,..

문제 (https://www.acmicpc.net/problem/2776) 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 10816번 (숫자 카드 2) 문제와 매우 비슷한 문제이다! 이 문제도 upper_bound, lower_bound를 사용하여 해결했다. upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 [소스코드] 더보기 2021-12-19 Silver 4 - 자료 구조 - 정렬 - 이분 탐색 - 해시를 사용한 ..

문제 (https://www.acmicpc.net/problem/2343) 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 실수했던 점! - ans 초기화할 때 값은 10,000이 아닌 1,000,000,000으로 해야 함 - 블루레이의 개수가 꼭 M일 필요 없음 - cnt 초기화를 1로 해두면 편하다... 많이.... - M 모든 강의가 들어가지 않는 것이므로 mid 값이 커지도록 한다 [소스코드] 더보기 2021-12-19 Silver 1 - 이분 탐색 - 매개 변수 탐색

문제 (https://www.acmicpc.net/problem/10816) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net upper_bound()와 lower_bound를 사용하여 푼 문제! 기억하기~~~ upper_bound: 처음으로 value 값을 초과하는 원소의 주소 lower_bound: value 값 보다 크거나 같은 첫 번째 원소의 주소 upper_bound 리턴 값 - lower_bound 리턴 값 0: value 값이 존재하지 않는 것 양수: value 값의..

문제 (https://www.acmicpc.net/problem/1654) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 전에 올린 나무 자르기와 비슷한 듯 다른 문제..! 나는 end 값을 입력받은 길이 중 가장 큰 값이 아닌 모든 길이의 합을 n으로 나눈 값으로 정했다. 각 길이를 mid로 나누었을 때 몫의 합이 n보다 - 크거나 같다면? 랜선의 길이를 더 길게 start 이동, 최댓값이라면 답으로 설정 - 작다면? 랜선의 길이를 더 짧게 end 이동 [소스코드] 더보기 20..

문제 (https://www.acmicpc.net/problem/2805) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색하는 값 (mid): 절단기의 높이 절단기의 높이가 mid일 때, 나무를 자르고 남은 길이들의 총합이 m 이상이면? - 더 큰 mid 값으로 m 이상을 구할 수도 있으므로 start를 mid + 1로 지정한다. [소스코드] 더보기 2021-05-25 Silver 3 - 이분 탐색 - 매개 변수 탐색

문제 (https://www.acmicpc.net/problem/2512) 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색하는 값 (mid): 예산 저번에 푼 1920번 문제는 배열의 인덱스를 이분 탐색으로 찾아냈다면 이 문제는 인덱스가 아니라 값들을 이분 탐색으로 찾아야 한다. 예산 요청의 총합이 m보다 크다면 이분 탐색을 진행한다. 이분 탐색을 진행할 때마다 sum을 구해야 하는데, 요청 금액이 mid 값보다 크다면 mid 값으로 더해주어야 한다. 배정된 예산들 중 최댓값인 정수를 출력해주..

문제 (https://www.acmicpc.net/problem/1920) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색이 잘 기억이 안 나서 전에 풀었던 문제들 글을 써보려 한다 🤦‍♀️ 이 문제는 간단한 이분 탐색 문제로 숫자들의 존재 여부를 1/0으로 출력해주면 된다. [소스코드] 더보기 2021-05-25 Silver 4 - 이분 탐색