이세계개발자의 개발일지

이번 문제는 11723번 집합문제이다.접근법1. 원소 범위가 작다 → 배열 또는 비트마스크 사용 가능원소 범위: 1 ≤ x ≤ 20집합 전체를 표현하는 데 21칸짜리 배열 또는 정수형 1개로 충분함2. 연산이 많다 → O(1) 시간 복잡도 필수find(), erase()가 포함된 STL vector나 set 사용 시 시간 초과 발생모든 연산을 상수 시간에 처리해야 함 1차 코드int 형의 vector를 사용해서 find, erase 등의 메서드를 사용하여 구현 > 시간복잡도 O(n) TLE#include using namespace std;int main(){ ios::sync_with_stdio(false); long long num; cin >> num; vector v; ..

이번 문제는 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)..

이번 문제는 1654번 랜선 자르기 문제이다.접근법가지고 있는 랜선을 잘라 같은 길이의 원하는 개수로 만드는 문제이다. 이 문제에서는 주어진 랜선의 개수가 만개 만들어야 할 랜선의 개수가 최대 100만개 이하로 주어지기에 브루트포스를 사용한다면 TLE 가 발생하는 것을 볼 수 있다.따라서 랜선의 최소 길이를 1, 최대 길이를 가장 긴 랜선으로 설정한 후 길이를 이분탐색을 사용하여 찾아내면 TLE가 발생하지 않고 원하는 값을 찾아내는 것을 볼 수 있을 것이다.추가적으로 이 문제에서는 랜선의 최대 길이가 2의 32승 -1 까지이기에 길이와 관련된 변수들을 long long으로 설정해야 함을 주의해야 한다.작성코드# include using namespace std;int main (void){ ios:..

이번 문제는 10815번 숫자카드 이다.접근법최대로 상근이가 가지고 있는 숫자카드의 개수가 500,000개 판별해야 할 숫자카드의 개수가 500,000개이기에 이를 브루트포스로 푼다면 250억번의 연산이 필요하게 된다. 따라서 이를 해결하기 위해 상근이가 가지고 있는 숫자카드를 정렬한 후 알고리즘 라이브러리의 바이너리 함수을 통해 이분탐색으로 해당하는 값이 있는지 없는지를 판별한다면 TLE가 발생하지 않고 문제를 해결할 수 있다.작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector v1; vector v2; for (int i..

이번 문제는 2805번 나무 자르기 이다.접근법이 문제는 이분 탐색을 사용해서 가장 높이 자를 수 있는 지점을 찾아내는 문제이다. 이분 탐색과 관련된 자세한 설명을 보고 싶으면 아래 글을 참고할 수 있다.2025.07.25 - [매일 BOJ] - (매일 BOJ) C++ 2512번 예산 (매일 BOJ) C++ 2512번 예산이번 문제는 2512번 예산 문제이다.접근법이 문제의 알고리즘 분류를 까보면 이분탐색 활용해야 한다고 작성되어 있다. 따라서start 값은 1,end 값은 예산 요청에서 가장 큰 값으로 설정한 후 for문norepinephrine.tistory.com 작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0..

이번 문제는 2512번 예산 문제이다.접근법이 문제의 알고리즘 분류를 까보면 이분탐색 활용해야 한다고 작성되어 있다. 따라서start 값은 1,end 값은 예산 요청에서 가장 큰 값으로 설정한 후 for문 안에서 sum 변수를 만들어 start와 end값을 기준으로 생성된1) mid값보다 작으면 예산값을 더하고2) mid값보다 크면 mid 값을 더하는 방식으로 처리했다. 이분탐색# 핵심 개념정렬된 배열에서만 사용할 수 있음 (오름차순/내림차순 모두 가능)탐색 범위를 반으로 줄여가며 원하는 값을 찾음중간값(mid)을 기준으로 원하는 값이 왼쪽에 있는지, 오른쪽에 있는지를 판단# 기본 구조int binary_search(vector& arr, int target) { int left = 0; ..