0-1 knapsack 문제란 배낭에 담을 수 있는 무게에 서로 무게가 다른 값어치의 물건을 담는다고 할 때 가방에 담을 수 있는 최대 값를 계산하는 방법이다.knapsack 문제는 Fractional knapsack 과 0-1 knapsack 두개 가 있는데Fractional knapsack은 쪼개서 일부 선택 가능한 knapsack 문제이고0-1 knapsack : 아이템을 0개 또는 1개만 선택할 수 있는 경우이다.0-1 knapsack 관련 문제를 푸는 이유이 중에서 DP에 대한 개념을 더 잘 이해하기 위해 0-1 knapsack을 고르게 되었다.0-1 knapsack을 그리디로 풀어서는 안되는 이유가방의 무게가 50일때 물건들이 다음과 같은경value : 60 , 100 , 120weight :..

LIS (Longest Increasing Subsequence)최장 증가 부분 수열→ 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출 하는 문제1. LIS란?주어진 순열에서 오름차순 을 유지하는 부분 수열 중 가장 긴 수열의 길이를 구하는 알고리즘ex) 수열 = [10, 20, 10 ,30 ,20 ,50] 이 주어졌을때가능한 증가 부분 수열은[10, 20, 30, 50] → 길이가 4[10, 20, 50] → 길이가 3[10, 30, 50] → 길이가 3등등이 생성된다. 이럴 경우 정답이 42. 대표적인 풀이방법풀이방법1 : DP풀이방법2 : 이진 검색 활용DP O(N^2) 풀이 - 기초적인 방법아이디어 : dp[i] = i..