조합 수학과 구성 문제의 심화 분석
기본 조합 계수 문제
문제는 특정 조건을 만족하는 정점 집합의 개수를 세는 것으로, 주로 그래프 구조와 조합적 성질을 활용한다. 예를 들어, 트리에서 두 하위 트리의 크기가 k/2인 경우를 찾는 것은 이진 분할 기반의 조합 계산으로 해결 가능하다. 각 간선에 대해 양쪽 끝점이 모두 "좋은 점"일 확률을 계산하고, 이를 전체 가능한 선택지 중에서 비율로 표현하면 된다 ...
7월 13일 03:26에 게시됨
차분 제약 시스템: 그래프 이론으로 푸는 부등식 문제
여러 개의 선형 부등식으로 표현된 제약 조건 하에서 각 변수의 최댓값이나 최솟값을 구해야 할 때, 그래프 이론의 최단경로/최장경로 알고리즘을 활용할 수 있다. 이를 차분 제약 시스템(Difference Constraints System)이라 한다.
핵심 원리: 부등식의 방향성
부등식 xi ≤ xj + ck는 정점 j에서 정점 i로 가는 가중치 ck의 유향 간선으로 해석한다.
목표그래프 해석 ...
7월 11일 02:13에 게시됨
알고리즘 노트 및 문제 해결 전략
P2569 https://www.luogu.com.cn/problem/P2569
이 문제를 참고하세요.
/*단조큐로 dp 최적화
주식을 매수하는 전이 방정식에서 j는 순차적으로 열거됩니다. 주식을 매수하는 것이므로 보유한 주식은 점점 증가할 것이며,
현재의 결정이 나중에(j가 더 클 때) 사용될 수 있으므로 먼저 구해야 합니다.
마찬가지로 주식을 매도할 때 보유한 주식은 점점 줄어들고,
즉 현재 ...
6월 27일 03:51에 게시됨
격자 동물 문제의 완전 탐색 풀이
문제 개요
격자 동물(Lattice Animals) 문제는 주어진 크기의 격자 내에서 특정한 연결된 블록 조합의 수를 세는 문제입니다. 이 문제는 복잡한 알고리즘 없이도 완전 탐색을 통해 해결할 수 있으며, 사전에 가능한 모든 경우를 계산하여 표 형태로 저장한 후 질의에 따라 바로 답을 출력하는 방식으로 구현됩니다.
접근 방법
해당 문제는 가능한 모든 연결된 블록의 형태 ...
6월 3일 00:41에 게시됨