목록동적계획법 (1)

코젤브

7주차 - 동적계획법 (백준 2579번)

동적계획법(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다. 부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. ex) 피보나치, 정수삼각형, 이항 계수 상향식 해결법(Bottom-Up 방식) 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 최적의 원칙 : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다. 백준 2579번: 계단 오르기 #include #define MAX 301 using namespace std; int main() { int n; int DP[301];..
컴공의 일상/백준 문제 2022. 5. 25. 19:41
이전 Prev 1 Next 다음