다이나믹 프로그래밍 기초: 배낭 문제의 핵심 전략
배낭 문제의 기본 구조와 최적화 원리
다이나믹 프로그래밍에서 배낭 문제는 상태 전이를 이해하는 데 중요한 예시입니다. 주요 유형은 0/1 배낭, 무한 배낭, 다중 배낭, 분할 배낭 등으로 나뉩니다. 각각의 차이는 선택 가능한 횟수와 제약 조건에 따라 달라집니다.
기본적인 상태 정의
dp[i][j]는 처음 i개의 아이템 중에서 총 용량이 j 이하인 조건에서 얻을 수 있는 ...
7월 25일 19:32에 게시됨
두 개의 고정 길이 구간으로 얻을 수 있는 최대 상품 수
문제 설명
수직선 위에 여러 개의 상품이 위치해 있으며, 각 상품의 좌표는 비내림차순으로 정렬된 배열 prizePositions로 주어집니다. 같은 위치에 여러 상품이 있을 수도 있습니다. 또한 정수 k가 주어지며, 이는 선택할 수 있는 두 개의 닫힌 구간 각각의 길이를 의미합니다 (즉, 구간의 길이는 정확히 k여야 함).
목표는 두 개의 길이 k인 구간을 선택하여 포함되는 ...
7월 9일 23:06에 게시됨
AGC005 문제 해설
A - STring
스택을 이용한 시뮬레이션으로 해결합니다. 문자열을 순회하면서 'S'는 스택에 추가하고, 'T'가 등장할 때 스택 상단이 'S'이면 제거합니다. 최종적으로 남은 스택 크기가 정답입니다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
string str;
cin >> str;
stack<char> stk;
for (char c ...
5월 31일 02:30에 게시됨