DP

▶ BufferedReader, 동적 계획법 DP를 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 동적 계획법의 첫번째 문제입니다. 피보나치 수 알고리즘으로 풀이하면 시간 초과가 발생합니다. 먼저 dp 배열을 long타입 전역변수로 초기화합니다.  main문에서 dp를  입력된 N+1만큼의 크기를 가지도록 초기화를 해줍니다. N+1로 배열을 만드는 이유는 동적 계획법(DP)을 사용하여 피보나치 수열을 계산할 때, 0번째부터 N번째까지의 피보나치 수를 저장할 공간을 확보하기 위해서입니다. 즉, 인덱스를 0부터 N까지 사용하기 위해 배열의 크기를 N+1로 설정하는 것입니다. 그리고 속도를 빠르게 하기 위해서 메모이제이션을 할 수 있도록 상향식 dp_fibo 함수를..

동적 계획법 DP란❓  동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.  주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다. 위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장동일 결과 재사용 DP 문제 성립 조건동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다. 최적 부분 구조(Optimal Substructure)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..