동적 계획법(DP)의 핵심 유형 정리: 배낭 문제부터 트리 DP까지
1. 01 배낭 문제 (01 Knapsack Problem)
01 배낭 문제는 DP의 가장 기초적인 형태 중 하나입니다. 주어진 물건들이 각각 무게와 가치를 가지고 있을 때, 배낭의 용량을 초과하지 않으면서 가치의 합을 최대화하는 것이 목표입니다. 각 물건은 단 하나씩만 존재하므로 '선택한다(1)' 또는 '선택하지 않는다(0)'의 두 가지 상태만 가집니다.
일반적으로 2차원 배열로 표현할 ...
10월 26일 13:36에 게시됨
AI 알고리즘 문제 해결 전략 및 C++ 구현 분석
선형 회귀 및 경사 하강법 구현
데이터 정규화 후 경사 하강법을 사용하여 가중치와 편향을 업데이트하는 문제입니다. 특징은 그래디언트 누적 시 위치를 정확히 파악하여 3 번의 연산이 이루어지도록 해야 한다는 점입니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double Real;
void executeProblem() {
co ...
10월 17일 06:48에 게시됨
기능적 그래프와 전처리 정렬을 활용한 동적 계획법 최적화 기법
그리드 기반 사각형 조합 탐색
그리드 환경에서 특정 조건을 만족하는 부분 도형을 탐색하는 문제에서는 각 도형의 가능한 배치 위치를 체계적으로 분류한 후, 이전 단계의 상태 정보를 기반으로 현재 위치로의 효율적인 전이를 수행하는 접근법이 유용합니다. 불필요한 중복 계산을 방지하기 위해 필요한 파라미터들을 미리 계산해 두면, 단위 위치당 $O(N)$ 시간 복잡도 ...
10월 3일 09:45에 게시됨
알고리즘 문제 해설: 모듈로 합, 그래프 연결성 및 구간 쿼리
CF577B: Modulo Sum
주어진 수열에서 연속되지 않은 부분 수열을 선택하여 그 합이 특정 수 m으로 나누어 떨어지는지 판단하는 문제입니다.
해결의 핵심은 비둘기집 원리 (Pigeonhole Principle) 에 있습니다. 수열의 길이 n이 모듈로 값 m보다 크다면,PREFIX 합을 m으로 나눈 나머지는 총 m가지 경우しか 존재하지 않습니다. 따라서 n > m인 상황에서는 반드시 같은 나 ...
9월 17일 02:29에 게시됨
블루브리ッジ 컵 국선 동적 프로그래밍 문제 해설
1. 정수 합 구성 문제 (2022)
서로 다른 10 개의 양정수를 선택하여 그 합이 2022 가 되는 경우의 수를 구하는 문제입니다. 이는 제한 조건이 두 개 존재하는 배낭 문제 변형으로 볼 수 있습니다.
접근 방식
1 부터 2022 까지의 숫자를物品으로 간주합니다. 각 숫자는 그 자체의 값을 비용 (weight) 으로 가지며, 선택된 숫자의 개수도 제한 조건이 됩니다. 따라서 상태 공 ...
9월 2일 04:17에 게시됨
AtCoder ABC 365 문제 A-E 상세 해설 및 구현 전략
A - 윤년 계산
문제 요약
입력으로 받은 연도 n을 기준으로 해당 연도의 일수가 365 일인지 366 일인지 판단해야 합니다.
해결책
윤년 여부를 판별하는 논리식을 적용하면 됩니다. 일반적으로 다음 규칙이 성립합니다:
4 로 나누어 떨어지지 않는 경우 평년입니다.
400 으로 나누어 떨어지는 경우 윤횔입니다.
100 으로 나누어 떨어지지 않으면서 4 로 나누어 떨어지는 경 ...
8월 16일 16:02에 게시됨
AGC007 문제 풀이
A - Shik and Stone
시작점 \((1, 1)\)에서 경로를 시뮬레이션하며 이동하면 된다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15;
string grid[MAX_N];
bool visited[MAX_N][MAX_N];
int main() {
int rows, cols;
cin >> rows >> cols;
string padding(cols + 2, '.');
grid[0] = grid[rows + 1] = pad ...
8월 6일 23:41에 게시됨
Codeforces Round 903 (Div. 3) 풀이
이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다.
A. Don't Try to Count
문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다.
#include <bits/stdc++.h>
using namespace std;
bool isSubstr(const s ...
7월 31일 23:32에 게시됨
문자열 부분 수열 판별: 단순 풀이부터 대용량 최적화까지
문제 정의
두 개의 문자열 source와 target이 주어질 때, source가 target의 부분 수열(subsequence)인지 판별하라. 두 문자열은 모두 소문자 알파벳으로 구성된다.
부분 수열은 원본 문자열에서 일부 문자를 제거하되(0개도 가능), 남은 문자의 상대적 순서를 유지하여 만들 수 있는 문자열이다. 예를 들어 "ace"는 "abcde"의 부분 수열이지만 "aec"는 아니다.
확장 시나 ...
7월 30일 14:13에 게시됨
다이나믹 프로그래밍 복습 노트
배낭 문제와 동적 계획법
대부분의 배낭 문제들은 01 배낭으로 변환한 후 복잡도를 최적화하는 방식으로 접근한다.
01 배낭 문제
각 물건은 선택하거나 선택하지 않는 두 가지 경우만 존재한다. 0과 1의 관계에 해당하기 때문에 01 배낭이라고 명칭한다.
dp[i][j]를 앞에서부터 i개의 물건 중容量 j의 배낭이 담을 수 있는 최대 가치라고 정의하자.
i번째 선택지는 i- ...
7월 24일 23:22에 게시됨