문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다. 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.퇴사일 이후로 상담이 넘어가면 해당 상담은 수행할 수 없습니다.최대 수익을 구하기 위해 DP를 활용합니다. 문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다. 특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하..
동적 계획법
문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 포도주 시식" 문제는 포도주가 1 ~ n개 있을 때 아래의 조건을 만족하는 가장 많은 양의 포도주를 마실 수 있는 양을 출력하는 문제입니다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.즉, 순서대로 포도주를 마실때 최대의 포도주 양을 구하면 되는 문제입니다. 문제의 핵심은 연속해서 3잔을 마실 수 없을 때 최대의 포도주 양을 구하는 것이 기 때문에, 이 점을 고려해야합니다. 위와 같이 테이블에 연속된 포도주가 [6, 10, 13, 9, 8 ,1]이 있을 때 마실 수 있는 최대의 포도주의 양은 첫 번째, 두 번째, 네 번째, 다섯 번째 포도..
문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 연속합"문제는 주어진 배열에서 연속된 수들의 합이 최대가 되는 부분 배열의 합을 구하는 문제입니다. 이 때 수열에서 숫자를 선택할 때는 연속된 수를 선택해야하는 것이 핵심입니다. 이 문제를 효율적으로 해결하기 위해 다이나믹 프로그래밍 알고리즘을 사용합니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다. 주로 줄여서 DP라고 많이 말하며, 주pixx.tistory.com 연속된 값을 선택해야 하므로, 현재까지의 연속합에 현재 값을 더한 값과 현재 ..
문제설명입력 & 출력나의 풀이문제 접근 방법 7 3 8 8 1 0 2 7 4 44 5 2 6 5 "백준 - 정수 삼각형"문제는 위와 같은 정수 삼각형에서 맨 위층에서 시작해서, 아래에 있는 수를 선택하여 마지막 레벨까지 도착했을 때 최대 합을 구하는 문제입니다. 이 때 아래에 있는 수는 왼쪽 대각선 또는 오른쪽 대각선만 선택할 수 있습니다. 이 문제를 해결하기 위한 핵심은 동적 계획법 (DP)을 사용하는 것입니다. 삼각형에서 각 정점마다 그 위치까지 올 수 있는 최대 합을 계산하여, 결국 맨 아래까지 내려오면서 최대 합을 구하는 방식입니다. [Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기동..