다이나믹 프로그래밍 문제 풀이 모음
목차
백준 4933 - 마스터 (선형 DP)
백준 5858 - 황금 검 (선형 DP)
백준 1280 - 닉의 임무 (선형 DP)
USACO 2016 오픈 - 2048 (구간 DP)
백준 2585 - 삼색 이진 트리 (트리 DP)
백준 1441 - 추 저울질 (조합 탐색 + 배낭)
백준 1896 - 서로 공격하지 않음 (비트마스크 DP)
Codeforces 1488E - 회문 쌍 (LIS 응용)
Codeforces 1486D - 최대 중앙값 (이분 탐색)
Codeforces ...
7월 9일 04:00에 게시됨
2025년 광저우대학교 프로그래밍 경진대회 신입생 대회
A 마법 문 Trial
크기 비교 문제, 난이도 1성
#include <iostream>
using namespace std;
int main()
{
int x, y, z, w;
cin >> x >> y >> z >> w;
if (x < w && y == z)
cout << "YES";
else
cout << "NO";
return 0;
}
B 약초 채집사
약초를 수집 ...
6월 27일 06:21에 게시됨
선분 트리 병합을 이용한 [FJOI2018] 지도자 그룹 문제 해결
먼저 이 문제는 그리디로 풀기 어려우므로 동적 계획법(DP)을 고려할 수 있습니다.
처음에는 \(dp_{i, j}\)를 \(i\)번 노드를 루트로 할 때 선택된 노드 중 최소 가중치가 \(j\)인 최대 멤버 수로 정의하는 직관적인 방법이 있습니다. 하지만 이 방법은 \(O(n^3)\)의 시간 복잡도를 가집니다. 많은 전이 과정이 동일하므로 비효율적입니다. 더 빠른 전이를 위해 상태를 변 ...
6월 25일 01:53에 게시됨
:NOIP 시뮬레이션 경진대회 문제 풀이
T1 다채로운 색상
문제는 다음과 같습니다:
nxm 크기의 행렬이 주어집니다.
(i,j) 위치에는 색깔 ci,j가 있습니다.
네 모서리의 색상이 모두 동일하지 않은 모든 하위 행렬의 수를 구하세요.
시간 복잡도 O(n²m)으로 해결할 수 있습니다. 두 행을 선택한 뒤 열을 스캔하면서 해당 열의 값들이 같으면 답에 기여할 가능성이 있습니다. 이를 위해 카운트 배열을 ...
6월 17일 19:19에 게시됨
Codeforces Round #574 (Div. 2) 기술 블로그 및 문제 풀이
Problem A: Drinks Choosing
N명의 학생들이 각자 선호하는 음료 맛이 있습니다. 총 $\lceil n/2 \rceil$개의 세트가 제공되며, 각 세트에는 같은 맛의 음료 2병이 들어 있습니다. 목표는 최대한 많은 학생이 자신이 원하는 맛의 음료를 받을 수 있도록 배분하는 것입니다.
가장 효율적인 방법은 동일한 맛을 원하는 학생들을 2명씩 묶어 한 세트를 주는 것입니다. 이렇게 ...
6월 14일 17:30에 게시됨
중산 집중 훈련 기록 (7.28–8.11)
7월 29일
주로 모의고사 중심으로 진행되었으며, 일부 문제에 대한 분석과 후기 포함.
T1
간단한 시뮬레이션 문제. CSP-S2023 T3보다도 쉬웠다. 디버그 문구를 지우지 않아서 실수했지만, 다행히 오답은 아니었다. 복잡도가 높을 수 있다는 점을 인지하고, 더 효율적인 접근 방식을 고려해야 한다. 결국 코드는 통과했으나, 조건이 애매하면 예외 처리가 필요하다.
T2
초기 ...
6월 11일 20:47에 게시됨
문자열 편집 거리와 서브시퀀스 개수 구하기: 동적 계획법 완전 정복
이번 글에서는 문자열 처리를 위한 동적 계획법(DP)의 세 가지 핵심 문제를 살펴보겠습니다. 각 문제는 이전 문제의 개념을 확장하여 최종적으로 편집 거리(Edit Distance) 문제를 해결합니다.
1. 서로 다른 서브시퀀스 개수
문자열 s와 t가 주어졌을 때, s의 서브시퀀스 중 t와 동일한 것의 개수를 구합니다. 편집 거리 개념에서 '삭제'는 긴 문자열의 문자를 제거하는 ...
6월 6일 16:59에 게시됨
문제 해결을 위한 알고리즘 접근
A 문제
링크
연속된 두 개의 '달콤한' 요소가 있으면 나머지 요소들을 모두 먹을 수 없습니다.
코드 보기
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string dishes[105];
for (int i = 0; i < n; ++i) {
cin >> dishes[i];
if (i > 0 && ...
5월 28일 19:00에 게시됨