이세계개발자의 개발일지

이번 문제는 2776번 암기왕이다.접근법주어진 수첩 1의 숫자 리스트에 대해 수첩 2의 각 숫자가 존재하는지를 빠르게 판단해야 한다.단순한 선형 탐색은 시간 초과되므로, 이분 탐색 또는 해시셋을 사용해야 한다. 알고리즘 설계수첩 1의 숫자들을 오름차순 정렬수첩 2의 각 숫자에 대해 이진 탐색 수행시간 복잡도정렬: O(N log N)M개의 숫자에 대해 각각 O(log N) → 총 O(M log N) 작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); long long T; cin >> T; for (int i = 0; i > N; vector v1; for..

이번 문제는 17266번 어두운 굴다리이다.접근법특정 밝기 거리 X를 기준으로, 가로등들이 굴다리 전체를 커버할 수 있는지를 확인한다.이분 탐색을 통해 최소한의 X를 찾는다.알고리즘 설계이분 탐색 범위는 start = 1, end = NX가 주어졌을 때, 가로등이 굴다리 [0, N]을 모두 커버할 수 있는지를 판단판단 기준첫 번째 가로등이 0보다 멀면 안 됨 → pos[0] - X > 0이면 실패두 가로등 사이가 비면 안 됨 → pos[i+1] - pos[i] > 2 * X이면 실패마지막 가로등이 끝까지 도달해야 함 → pos.back() + X 작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0)..

이번 문제는 16401번 과자 나눠주기 문제이다.접근법어떤 길이 L로 자를 경우, 각 과자로 만들 수 있는 조각 수는 과자 길이 / L이다.모든 과자에 대해 이 값을 합산한 결과가 M 이상이면 해당 길이로 나눠주는 것이 가능하다.이분 탐색을 통해 가능한 최대 길이 L을 찾는다.알고리즘 설계입력된 과자 길이를 배열에 저장한다.탐색 범위는 start = 1부터 end = max(과자 길이)까지로 설정한다.이진 탐색을 수행하며, mid를 현재 시도하는 과자 길이로 간주한다.각 과자마다 길이 / mid를 계산하여 총 몇 개의 조각을 만들 수 있는지 확인한다.총 조각 수가 M 이상이면 길이를 더 늘려볼 수 있으므로 start = mid + 1, 답을 갱신한다.그렇지 않다면 end = mid - 1로 범위를 줄인다..

이번 문제는 1072번 게임이다.접근법이 문제는 정수 승률이기 때문에 변화가 일어나지 않을 수도 있다. 예를 들어,현재 승률이 80%일 때, 1~수십 판 이겨도 여전히 정수 승률은 80%일 수 있다.또한, 최대 10억 판 이상을 더 해야 바뀔 수도 있으므로 완전 탐색은 불가능하다.따라서 이진 탐색(Binary Search)을 이용한다. 알고리즘 설계현재 승률 Z를 계산한다: Z = (Y * 100) / XZ가 99 이상이면, 승률은 절대 1 이상 증가할 수 없으므로 -1 출력1부터 10억까지 이분 탐색 범위를 설정mid값을 더 이긴 경기 수로 가정하고, 새로운 승률을 계산새 승률이 Z보다 크면 정답 후보로 저장하고, 더 적은 mid를 탐색아니면 mid를 증가시킴최솟값을 찾아 출력작성코드# include ..

이번 문제는 2343번 기타 레슨 문제이다.접근법이 문제는 흔히 말하는 이분 탐색으로 정답을 찾는 문제 이다.즉, 정답이 될 수 있는 범위를 두고, 그 안에서 가능한지 아닌지를 판별하면서 범위를 좁혀나가는 방식으로 해결해야 한다.따라서 이 문제에서는 블루레이 크기를 정해놓고, 그 크기로 강의들을 나눴을 때 M개 이하로 블루레이가 필요한지 확인해야 한다. 여기서 이분탐색의 시작과 끝 값은 이러하다. start = 가장 긴 강의의 길이→ 블루레이 크기는 최소한 이 정도는 되어야 함end = 모든 강의의 총합 → 모든 강의를 하나에 담는다면 이게 최대그 후 mid 를 (start + end) / 2 로 설정하고 아래의 의사코드를 구현하면 된다.for (각 강의) { if (현재 누적 + 강의 > mid)..