DP

문제설명입력 & 출력 나의 풀이 이번 문제는 피보나치 N에서 0과 1의 개수를 출력하는 문제입니다. 피보나치수열은 워낙 유명하기 때문에 어렵지 않게 풀 수 있지만 이 문제는 기존의 피보나치 함수를 재귀호출로 푼다면 런타임 에러가 발생합니다. 따라서 동적 계획법(DP)를 사용해야 합니다. 먼저 피보나치 함수를 점화식으로 표현한다면 다음과 같습니다.F(n) = F(n-1) + F(n-2)위 점화식을 기준으로 이미 계산된 값들을 배열에 저장하여 중복된 계산을 방지해야 합니다. 먼저 dp배열을 초기화해줍니다. 첫 번째 배열은 피보나치 수의 인덱스이며, 두 번째 배열은 크기가 2를 가지는 데 0번째는 0의 개수, 1번째는 1의 개수가 들어가게 됩니다. 이제 fibo(0)과 fibo(1)은 이미 값이 정해져 있기 ..

▶ 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)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..