동적 프로그래밍을 활용한 배낭 문제 해결
기본 배낭 문제
배낭의 최대 용량과 다양한 무게 및 가치를 가진 아이템들이 주어졌을 때, 배낭에 담을 수 있는 최대 가치를 구하는 문제입니다.
문제 설명
첫째 줄: 두 정수 M(배낭 용량)과 N(아이템 개수)
둘째 줄부터 N+1번째 줄까지: 각 아이템의 무게와 가치
출력: 배낭에 담을 수 있는 최대 가치
예시 입력
10 4
2 1
3 3
4 5
7 9
예시 출력
12
...
7월 6일 01:39에 게시됨
트리 DP와 비트마스크 DP 문제 풀이
P1352 상사 없는 파티
트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다.
상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값
점화식:
val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가)
val[node][0] = Σ max(val[child][0], ...
7월 3일 21:12에 게시됨
알고리즘 디버깅 노트: 실수에서 배우는 최적화
경험을 통해 배운 디버깅 사례들을 정리합니다. 비슷한 실수를 반복하지 않기 위한 기록입니다.
위상 정렬: 인덱스 실수
원본 코드:
while (front < rear) {
int cur = queue[front++];
for (int idx = adj[cur]; idx; idx = nxt[idx]) {
int nxtNode = to[idx]; // 정상
indeg[nxtNode]--;
if (indeg[nxtNode] == 0) {
...
6월 25일 21:08에 게시됨
문자열 동적 계획법: 부분 수열 카운팅, 삭제 연산, 그리고 편집 거리 최적화
1. 서로 다른 부분 수열의 개수 구하기
두 개의 문자열 text와 pattern이 주어졌을 때, text의 부분 수열 중 pattern과 일치하는 경우의 수를 계산하는 문제입니다. 부분 수열이란 원본 문자열에서 문자의 상대적 순서를 유지한 채 일부 문자를 제거하여 만들 수 있는 새로운 문자열을 의미합니다. 결과값은 32비트 부호 있는 정수 범위를 보장합니다.
class Solution {
pu ...
6월 16일 02:33에 게시됨
동적 계획법을 활용한 상태 머신 기반 문제 해결 전략
동적 계획법(Dynamic Programming)에서 상태 머신(State Machine) 개념을 도입하면 복잡한 의사결정 과정을 간결한 상태 전이 방정식으로 변환할 수 있습니다. 각 단계에서의 선택지를 상태로 정의하고, 이전 상태로부터 현재 상태로 도달하는 최적 경로를 계산하는 세 가지 사례를 살펴봅니다.
1. 인접한 항목을 선택할 수 없는 경우 (도둑 문제)
연속된 상점을 ...
6월 10일 16:04에 게시됨
NCPC 2018 문제 풀이 노트
2018년 노르딕 대학생 프로그래밍 콘테스트(NCPC 2018)의 문제들을 정리한 풀이 노트입니다. 각 문제의 핵심 아이디어와 구현 방식을 다룹니다.
A. 개구리 탈출
n마리의 개구리가 우물에 빠졌습니다. 각 개구리는 점프력, 체중(하부 지지 한도), 신장을 가지며, 서로를 밟고 올라가 우물을 탈출해야 합니다. 최대 몇 마리가 탈출할 수 있는지 구하는 문제입니다.
지지 한 ...
6월 9일 17:09에 게시됨
上海市计算机학회 경시대회 2023년 8월 월례丙조 T5 격자 경로
T5 격자 경로
메모리 제한: 256 Mb | 시간 제한: 1000 ms
문제 설명
n × m개의 격자로 이루어진 지도가 주어진다. 각 격자에는 지형 정보가 있다:
일부 격자는 벽(#)이며, 통과할 수 없다.
일부 격자는 길(.)이며, 통과할 수 있다.
좌상단 격자에서 시작하여 우하단 격자까지 최단 거리로 도착하는 경우의 수를 구해야 한다. 이동 중에는 벽 격자로 진입할 수 없으며, ...
5월 31일 13:16에 게시됨