순서를 고려하는 경우 고려하지 않는 경우 #include using namespace std; int N, K; int D[201][201]; int main(void) { cin >> N >> K; for (int i = 1; i

[목차] LIS란? LIS를 구하는 알고리즘 완전 탐색 알고리즘 분할 정복 백트래킹 두 완전 탐색 알고리즘의 비교 동적 계획법 알고리즘 O(N²) 풀이 이분 탐색을 이용한 풀이 두 동적 계획법 알고리즘 비교 세그먼트 트리 알고리즘 LIS의 대표 예제 전깃줄 문제 줄세우기 문제 합친 LIS 1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 여기서 잠깐 LIS의 S가 subarray가 아니라 subsequence의 이유를 보면 다음과 같다. 부분 수열의 종류는 크게 subarray와 subsequence가 있다. subarray는 연속적으로 이어져있는 부분 수..

1. 가장 긴 증가하는 부분 수열(LIS)이란? 증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서 LIS(Longest Increasing Subsequence)라고 한다. 이때 부분수열의 원소들은 주어진 원래의 배열처럼 이어져 있지 않아도 된다는 특징이 있다. 예를 들어 다음과같은 수열 S(n)을 보자. S(n) = {10, 20, 10, 30, 20, 50} 수열 S(n)에 대하여 다음과 같이 총 5개의 증가하는 부분 수열을 만들 수 있다. {10, 20, 30, 50} {20, 30, 50} {10, 30, 50} {30, 50} {20, 50} 이 중에서 LIS는 {10, 20, 30, 50}이 되는 것이다. 부분 수열 문제는 배낭 문제(knapsack problem)의..

https://shoark7.github.io/programming/algorithm/4-ways-to-get-subarray-consecutive-sum 최대 연속 부분수열 합을 구하는 4가지 알고리즘 I introduce 4 algorithms to get largest continuous sum of subarrays shoark7.github.io 1. 완탐 오앤제곱 2. DP on + 투 포인터???

1. 구간합이란? 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 개념 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다. 자연수 n에 대하여 수열 A(n)의 1 ~ n까지의 합을 S(n)이라고 할 때 두 자연수 a ~ b까지의 합은 S(b) - S(a-1)이다. [증명] a > a >> b; for (int i = 1; i > A[i]; //S(b), S(a) 구하기 for(int i=1; i Ai; S[i] = S[i-1] + Ai; } cin >> a >> b; cout