알고리즘/DP 썸네일형 리스트형 백준 1912번: 연속합 (JAVA) 문제 해석 n개의 정수로 이루어진 수열이 주어지고 수열 내에서 연속되는 몇 개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 알고리즘 DP를 이용하여 현재 위치의 수와 (현재 위치의 수 + 이전까지의 총합)을 비교하여 더 큰 값을 기억하도록 한다. 각 인덱스 별 DP 값 중에서 가장 큰 값을 출력한다. 코드 더보기 백준 2193번: 이친수 (JAVA) <다이나믹 프로그래밍> 문제 해석 자릿수 N이 입력값으로 주어질 때 만들 수 있는 N자리 이친수의 개수를 구해라 이친수의 첫자리는 1이며 1다음에는 무조건 0이 온다. 알고리즘 N=1인 경우 1 -> 1개 N=2인 경우 1 0 -> 1개 N=3인 경우 1 0 0 / 1 0 1 -> 2개 N=4인 경우 1 0 0 0 / 1 0 0 1 / 1 0 1 0 -> 3개 N=5인 경우 1 0 0 0 0/ 1 0 0 0 1 / 1 0 0 1 0 / 1 0 1 0 0 / 1 0 1 0 1 -> 5개 이를 통해 N번째인 경우 = N-1번째인 경우 + N-2번째인 경우 점화식을 도출할 수 있다. 다이나믹 프로그래밍 이와 같은 형태를 다이나믹 프로그래밍이라고 한다. 하나의 문제를 작은 문제로 쪼개어서 작은 문제의 결과들을 저장하고 이를 보다 큰 .. 더보기 이전 1 다음
