LeetCode 알고리즘 문제 분석: 이분 탐색을 이용한 최적해 도출 기법
문제 1: 일별 최대 작업 시간 최소화 (LCP 12)
특정 프로젝트 진행 시 전체 작업량을 $N$개의 과제들로 나누어 $M$일 동안 처리해야 하는 상황을 가정합니다. 각 과제에는 고유한 수행 시간이 존재하며, 반드시 순서대로 실행되어야 합니다. 다만, 매일 한 번씩 전문가의 도움을 받아 특정 과제의 소요 시간을 제로로 할 수 있는 기회가 주어집니다. 이 조건 하에서 $M$일 ...
7월 7일 04:35에 게시됨
Codeforces Edu Round 143 A-B 풀이 정리
A번: Two Towers
빨간색(R)과 파란색(B) 블록으로 구성된 두 개의 탑이 주어진다. 한 번의 이동에서는 길이가 2 이상인 탑의 꼭대기 블록을 다른 탑으로 옮길 수 있다. 이동을 통해 두 탑 모두 빨강-파랑이 번갈아 나타나는 형태로 만들 수 있는지 판별하는 문제다.
핵심 관찰
탑의 구조를 분석하면 몇 가지 중요한 사실을 발견할 수 있다:
각 탑 내부에서 인접한 동일 색 ...
7월 5일 00:34에 게시됨
NOIP 연습 세션 #1 상세 문제 풀이
문제 A: 점 쌍의 각도 최적화
이 문제는 두 점 사이의 관계를 최적화하는 전형적인 그리디 알고리즘 문제입니다. 데이터 범위를 고려했을 때 $O(n \log n)$ 시간 복잡도가 필요하며, 정렬을 활용해야 합니다.
핵심 아이디어는 좌표축을 45도 회전시키는 것입니다. 기존 좌표 $(x, y)$를 $(x+y, x-y)$로 변환하면, $y=x$ 또는 $y=-x$에 가장 가까운 값을 찾는 문제가 됩니 ...
6월 28일 01:33에 게시됨
USACO 2023년 2월 대회 브론즈 문제 해설
USACO 2023 February Contest, Bronze
1. 배고픈 소 (Hungry Cow)
매일 저녁에 소 베시(베시)는 창고에 건초가 있으면 한 개의 건초를 먹는다. 농부 존은 베시가 배고픈思いをしない 있도록 특정 날짜에 건초를 배달한다. 구체적으로, 날짜 di에 bi개의 건초가 아침에 배달된다. 첫 번째 T일까지 베시가 먹을 건초의 총 개수를 계산하는 문제이다.
문제 분석
각 날짜에 ...
6월 24일 18:56에 게시됨
ABC362 문제 해설
A 문제
문제는 매우 간단합니다. 세 정수 r, g, b와 문자열 c가 주어집니다. c가 "Red"이면 g와 b 중 최솟값을, "Blue"이면 r와 g 중 최솟값을, 그 외의 경우 r와 b 중 최솟값을 출력하면 됩니다.
코드 보기
#include<bits/stdc++.h>
using namespace std;
int main(){
int red, green, blue;
string color;
cin >> red > ...
6월 19일 01:43에 게시됨
Codeforces Round 979 Div. 2 문제 풀이
A 문제
첫 번째 위치의 기여도는 항상 0이다. 나머지 n-1개의 위치에서 최대값과 최소값을 첫 두 위치에 배치하면 최적의 결과를 얻을 수 있다. 이 경우 기여도는 (최대값 - 최소값) × (n-1)이 된다.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void process() {
int length;
cin >> length;
int high = INT_MI ...
5월 27일 01:34에 게시됨
NOIP 모의고사 4회 풀이 노트
문제 1: 대회 참가 조합
각 참가자의 대회 참가 여부를 비트마스크로 인코딩하여 [0, 16) 범위의 정수로 표현한다. 이후 각 상태의 비트 개수(popcount)를 기준으로 내림차순 정렬한 뒤, 그리디 전략으로 조합을 구성한다.
핵심 아이디어는 sum[j]가 양수일 때, 현재 상태 j와 겹치지 않는 참가자를 병합하여 새로운 상태를 형성하는 것이다. 초기값을 충분히 큰 값으로 설 ...
5월 25일 10:19에 게시됨
XOR 선형 기저(Linear Basis)의 이해와 구현
1. 선형 기저(Linear Basis)의 정의와 성질
집합 $S$에 대한 XOR 선형 기저 $B$는 $S$의 부분집합 XOR 합으로 만들 수 있는 모든 값의 집합을 동일하게 생성할 수 있는 최소 크기의 집합입니다. 선형 대수학에서의 기저(Basis) 개념을 XOR 연산과 벡터 공간 $GF(2)^n$으로 가져온 것이라 이해할 수 있습니다.
선형 기저는 다음과 같은 핵심 성질을 가집니다.
원래 수 ...
5월 24일 16:01에 게시됨