목재 조각 분할 최적화
문제 개요
길이가 각각 $ L_i $인 $ n $개의 나무 막대가 연속적으로 연결되어 있습니다. 이 중에서 최대 $ m $개의 접합부를 자를 수 있으며, 자른 후 만들어진 조각들 중 가장 긴 조각의 길이가 최소가 되도록 해야 합니다. 또한, 그러한 조합의 경우의 수를 구하고 결과를 $ 10007 $로 나눈 나머지를 출력해야 합니다.
해법 접근
이 문제는 두 가지 부분으로 나뉩니다: ...
8월 9일 08:44에 게시됨
단조 큐를 이용한 동적 계획법 최적화 기법
단조 큐를 통한 동적 계획법 최적화 개요
단조 큐는 특정 조건 하에서 무의미한 후보를 빠르게 제거함으로써 상태 전이의 효율을 높이는 강력한 기법이다. 특히, 결정의 범위가 항상 증가하거나 감소하는 경우, 즉 윈도우 크기가 고정되거나 단조롭게 변할 때 효과적이다. 이는 일반적으로 슬라이딩 윈도우 문제로 모델링 가능하며, 대부분의 최적화 패턴은 이 구조에 근 ...
8월 5일 20:39에 게시됨
이분 탐색을 활용한 배열 내 특정 값의 범위 찾기
정렬된 정수 배열 nums와 목표값 target이 주어졌을 때, 이 목표값이 처음 나타나는 위치와 마지막으로 나타나는 위치를 반환하는 문제입니다. 만약 목표값이 존재하지 않으면 [-1, -1]을 반환해야 하며, 알고리즘은 반드시 O(log n) 시간 복잡도를 가져야 합니다.
예시:
입력: nums = [5,7,7,8,8,10], target = 8
출력: [3,4]
초기 시도에서는 모든 일치하는 인덱스를 s ...
7월 10일 18:43에 게시됨
이분 탐색과 깊이 우선 탐색 기반 문제 해결
T1. 이분 탐색: 정렬된 배열에서 값 찾기
정렬된 배열 내에서 특정 값을 찾아 그 인덱스를 반환하는 문제입니다. 배열 크기가 최대 106까지 가능하므로, 배열 선언 시 크기를 충분히 확보해야 합니다.
오류 원인: 배열 크기 지정이 부족 (105+7로 설정했으나, 106+7 필요)
핵심 전략: 이분 탐색은 값이 일치할 경우에도 왼쪽 경계를 찾기 위해 r = mid로 업데이트
#inc ...
6월 25일 21:05에 게시됨
코드포스 라운드 988 (Div. 3) 문제 해설
A. 동일 숫자 페어 계산
배열 요소의 빈도를 저장하는 카운터를 활용하여 동일한 숫자 쌍의 최대 개수를 계산합니다. 각 숫자에 대해 발생 횟수를 2로 나눈 몫을 합산하여 해결합니다.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int testCase ...
6월 23일 03:04에 게시됨
트래킹 세그먼트 (이분 탐색, 구간 누적합)
문제 설명
n개의 0으로 초기화된 배열 a가 주어집니다. 또한 m개의 구간이 주어지며, 각 구간은 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 정의됩니다. 이는 배열 a의 부분 배열 a[l_i], a[l_i+1], ..., a[r_i]를 의미합니다.
특정 구간에서 1의 개수가 0의 개수보다 크다면 해당 구간을 아름다운 구간이라고 합니다. 예를 들어, a = [1, 0, 1, 0, 1]인 경우 구간 [1, 5]는 1이 3 ...
5월 31일 13:04에 게시됨
전화선 최소 비용 계산
문제 개요
농부 존은 자신의 농장에 전화선을 설치해야 한다. 그러나 통신사의 협조가 부족하여, 일부 전화선은 비용을 지불해야 한다.
전체적으로는 N (1 ≤ N ≤ 1,000)개의 전화 기둥이 있으며, 각각 1부터 N까지 번호가 매겨져 있다. 현재는 아무 기둥도 연결되어 있지 않다.
총 P (1 ≤ P ≤ 10,000)개의 기둥 쌍 사이에 전화선을 설치할 수 있으며, 나머지는 거리가 너무 ...
5월 22일 02:20에 게시됨