DP

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 연속합"문제는 주어진 배열에서 연속된 수들의 합이 최대가 되는 부분 배열의 합을 구하는 문제입니다. 이 때 수열에서 숫자를 선택할 때는 연속된 수를 선택해야하는 것이 핵심입니다. 이 문제를 효율적으로 해결하기 위해 다이나믹 프로그래밍 알고리즘을 사용합니다. [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) 알아보기동..

LIS이란 ❓LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)는 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 여기서 부분 수열이란, 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들을 선택한 새로운 수열을 말합니다. 증가하는 수열이란, 선택된 원소들이 항상 오름차순으로 배치되는 수열을 의미합니다.LIS 예시주어진 수열이 [10, 20, 10, 30, 20, 50]일 때, LIS는 [10, 20, 30, 50]입니다. 이 부분 수열은 주어진 수열의 원소들 중에서 가장 긴 증가하는 부분 수열로, 원래 수열의 순서를 유지하면서 오름차순으로 나열된 부분 수열입니다. LIS의 특징1. 부분 수열원래 수열에서 일부 원소들을 선택하여 만든 새로운 ..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 가장 긴 증가하는 부분 수열"문제가 처음에는 쉽게 이해가 되지 않았지만 알고보면 크게 어렵지 않은 문제입니다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다. 문제에서 나와있듯이 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 가장 긴 증가하는 부분 수열이라는 말은 주어진 수열에서 순서대로 (즉, 원래 수열의 순서를 유지하면서) 증가하는 수들 중에서 가장 긴 부분 수열을 찾는 문제입니다.  이때 "가장 긴"은 부분 수열의 길이를 의미하며, 반드시 연속된 원소일 필요는 없습니다. 즉, 예..