LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1, 7, 8, 5, 4, 9}의 배열이 있다면, LIS는 {3, 6, 7, 8, 9} 이다  DPLIS 문제는 각 요소를 포함하는 증가하는 부분 수열의 최대 길이를 찾는 문제로 이를 효율적으로 해결하기 위해 동적 계획법을 사용한다.단일 배열 내에서, 이전 인덱스의 숫자와 비교하여 증가시켜주면 되기 때문에 DP로 문제를 해결할 수 있다.단일 배열이라는 점만 제외하면 LCS와 유사한 매커니즘이기에, 점화식도 비슷한 방법으로 구현할 수 있다.   [알고리즘] LCS (Longest Common Subseque..

문제 링크 Silver 3 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 문제 티어는 낮지만 DP문제라서 냉큼 공부 처음에는 아래처럼 해당 idx의 제곱값을 구하여 greedy처럼 풀어내려고 했으나 int[] arr = new int[(int) Math.sqrt(n) + 1]; for (int i = 0; i < arr.length; i ++) { arr[i] = i * i; } 모든 상황에 만족하지 ..

https://leetcode.com/problems/minimum-path-sum/ Minimum Path Sum - LeetCodeCan you solve this real interview question? Minimum Path Sum - Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or rigleetcode.com 풀이이차원배열 grid에서, 오른쪽, 아래로만 이동할 수 있을 때, 모든 숫자의 합을 최소화 하는..