매일 조금씩

LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 풀이 1. DP로 풀기 시간 복잡도 O(N^2) 이기 때문에 원소의 개수가 작은 경우에는, 해당 방법으로 문제를 풀 수 있다. {10 20 10 30 20 50} 수열 1 2 3 4 5 6 10 20 10 30 20 50 DP[i] = i번째 원소를 포함하는 증가 수열의 최대 원소 개수 N=1 1 2 3 4 5 6 1 N=2 1 2 3 4 5 6 1 2 현재 index의 원소 값과, 그 미만의 index의 원소 값을 비교 현재 원소보다 작은 원소가 있다면 해당 index의 dp값 중 최대값에 + 1을 한 것..

배낭 문제 배낭 문제란 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 짐을 쪼갤 수 있는 경우에는 Fractional Knapsack Problem 으로 부르며, Greedy를 이용해 풀 수 있다. 짐을 쪼갤 수 없는 경우의 배낭문제는 0-1 배낭문제라고 부른다. 이 경우에는 DP를 이용해 문제를 풀 수 있다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C 배낭 문제 - 위키백과, 우리 모두의 백과사전 배낭 문제(Knapsack Problem 냅색 프라블럼[*])는 조합 ..