동적 계획법

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 이친수" 문제는 아래의 조건을 만족하는 수를 이친수라고 할 때 입력되는 N 자리수의 이친수 개수를 구하는 문제입니다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 즉, 위와 같이 0으로 시작하지 않고, 11을 부분 문자열로 가지지 않는 수를 구하면 되는 문제입니다. 이 문제의 조건을 자세히 살펴보면 2가지 핵심 요구사항이 있습니다.0으로 시작할 수 없다1이 연속으로 나타날 수 없다 (11을 부분 문자열로 가질 수 없다)이러한 조건을 바탕으로 이친수를 단계적으로 만들어보겠습니다. 1 자리 이친수 먼저 1자리 이친수는 "1"밖에 없습니다 (0으로 시작할 수 없으므로). 2 자리..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다. 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.퇴사일 이후로 상담이 넘어가면 해당 상담은 수행할 수 없습니다.최대 수익을 구하기 위해 DP를 활용합니다. 문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다. 특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 포도주 시식" 문제는 포도주가 1 ~ n개 있을 때 아래의 조건을 만족하는 가장 많은 양의 포도주를 마실 수 있는 양을 출력하는 문제입니다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.즉, 순서대로 포도주를 마실때 최대의 포도주 양을 구하면 되는 문제입니다. 문제의 핵심은 연속해서 3잔을 마실 수 없을 때 최대의 포도주 양을 구하는 것이 기 때문에, 이 점을 고려해야합니다. 위와 같이 테이블에 연속된 포도주가 [6, 10, 13, 9, 8 ,1]이 있을 때 마실 수 있는 최대의 포도주의 양은 첫 번째, 두 번째, 네 번째, 다섯 번째 포도..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 연속합"문제는 주어진 배열에서 연속된 수들의 합이 최대가 되는 부분 배열의 합을 구하는 문제입니다. 이 때 수열에서 숫자를 선택할 때는 연속된 수를 선택해야하는 것이 핵심입니다. 이 문제를 효율적으로 해결하기 위해 다이나믹 프로그래밍 알고리즘을 사용합니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓  동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.  주로 줄여서 DP라고 많이 말하며, 주pixx.tistory.com  연속된 값을 선택해야 하므로, 현재까지의 연속합에 현재 값을 더한 값과 현재 ..