다이나믹 프로그래밍
여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기
예제 - 백준 2 X n 타일링 (11726)
#include <bits/stdc++.h>
using namespace std;
int d[10005];
int mod = 10007;
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
d[1] = 1;
d[2] = 2;
for(int i = 3; i <= n; i++) d[i] = (d[i-1]+d[i-2])%mod;
cout << d[n];
}
결론
dp는 문제를 잘 파악해서 테이블과 점화식을 잘 설정하는 것이 키 포인트...!
문제 유형이 다양하기 때문에 최대한 많이 풀어보기
'algorithm > 정리' 카테고리의 다른 글
자바 기본 자료구조 선언 정리 (0) | 2024.04.09 |
---|---|
그리디 알고리즘 (0) | 2024.04.09 |
이분탐색 추가 - Upper Bound(상한), Lower Bound(하한) (0) | 2024.04.08 |
이분탐색 (0) | 2024.04.05 |
99클럽 코테 스터디 5일차 TIL - 자바 map 관련 함수 (getOrDefault, equals) (1) | 2024.04.05 |