목재 조각 분할 최적화
문제 개요
길이가 각각 $ L_i $인 $ n $개의 나무 막대가 연속적으로 연결되어 있습니다. 이 중에서 최대 $ m $개의 접합부를 자를 수 있으며, 자른 후 만들어진 조각들 중 가장 긴 조각의 길이가 최소가 되도록 해야 합니다. 또한, 그러한 조합의 경우의 수를 구하고 결과를 $ 10007 $로 나눈 나머지를 출력해야 합니다.
해법 접근
이 문제는 두 가지 부분으로 나뉩니다: ...
8월 9일 08:44에 게시됨
단조 큐를 이용한 동적 계획법 최적화 기법
단조 큐를 통한 동적 계획법 최적화 개요
단조 큐는 특정 조건 하에서 무의미한 후보를 빠르게 제거함으로써 상태 전이의 효율을 높이는 강력한 기법이다. 특히, 결정의 범위가 항상 증가하거나 감소하는 경우, 즉 윈도우 크기가 고정되거나 단조롭게 변할 때 효과적이다. 이는 일반적으로 슬라이딩 윈도우 문제로 모델링 가능하며, 대부분의 최적화 패턴은 이 구조에 근 ...
8월 5일 20:39에 게시됨
투 포인터 알고리즘 활용
파트너 매칭
남성과 여성의 매력도 배열에서 차이가 1 이하인 쌍의 최대 개수를 구합니다. 두 배열을 정렬한 후 포인터를 이동하며 매칭합니다.
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int maleArr[100], femaleArr[100];
int n, m, cnt = 0, i = 0, j = 0;
sort(maleArr, maleArr + n);
sort(femaleArr, ...
7월 29일 18:43에 게시됨
배열 파트02 - 코드 추적
시작 시간 10:30
최소 길이의 하위 배열
문제 제안: 이 문제의 핵심은 슬라이딩 윈도우 개념을 이해하는 것입니다. 텍스트 설명은 다소 복잡할 수 있으므로 동영상 강의를 먼저 참고하는 것이 좋습니다. 확장 문제는 우선 생략해도 됩니다.
문제 링크: https://leetcode.cn/problems/minimum-size-subarray-sum/
강의 자료: https://programmercarl.com/0209.길이-최소- ...
7월 15일 18:19에 게시됨
배열과 연결 리스트 알고리즘 기초
시간 복잡도
알고리즘 분석 시 시간과 공간 복잡도를 우선 고려합니다. O(n³) 이상의 복잡도는 실제 환경에서 비효율적입니다. n은 데이터 규모를 나타내며, 로그 복잡도(log n)는 연산 횟수가 데이터 크기에 로그적으로 비례함을 의미합니다.
배열
이진 탐색
정렬된 배열에서 중복 없을 때 적용 가능합니다. 탐색 구간을 반으로 축소하며 대상 값을 검색합니다.
class Bi ...
7월 11일 02:49에 게시됨