언제 사용할까

: 정해진 컨테이너의 순서를 해치지 않으면서, 오름차순으로 가장 길게 나열할 수 있는 집합을 만드려고 할때 사용한다.

• [3] 번 인덱스를 확인할때 앞에 있는 모든 인덱스를 확인하면서 가장 최대로 나열할 수 있는 것을 선택해야 하므로, 이중 포문을 사용해야 한다
  는 것을 떠올려야 한다.

관련 문제

• 김태원 dp 최대선 연결하기 : 빙빙 꼰 것처럼 보이지만 실상은 LIS 문제
• 김태원 가장 높은 탑 쌓기
• 백준 : https://velog.io/@kwt0124/%EB%B0%B1%EC%A4%8011053%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4
• 이코테 병사배치하기
• 구름 : jmos

맨날 까먹어서 만들었따.

https://www.youtube.com/watch?v=YWnOMETo4ww

가장 길게 증가하는 원소들의 집합을 만들어라

=> 그림을 그리고, 코드로 표현만 하면된다!
1) 0번째 값을 1로 설정해야겠다.
2) 1번째 인덱스값과 0번째 인덱스값을 비교하면서 dp[1]의 값을 갱신한다.
이때는 max를 이용해 가장 큰값으로 갱신하도록 한다.

//의사 코드
for(int i = 1; i < n; i++)
{
for(int j = i; j >= 0; j--)
{
//i는 갱신을 진행할 인덱스
if(v[i] < v[j])
{
d[i] = max(dp[j] + 1, dp[i]);

-> 이런식으로 +1을 하는 이유는 이전값의 dp갯수를 현재 들어오면서 + 1 갯수 증가시키는 것이다.

: 5,3,7,8,6,2,9,4 중 가장 긴 수열의 길이는?

• 모든 경우의 수
  5
  3

5 - 7
3 - 7

5 - 7 - 8
3 - 7 - 8

3 - 7 - 8 - 9
5 - 7 - 8 - 9
3 - 8 - 9
5 - 8 - 9

3 - 6
5 - 6
~~ 이렇게 나타낼 수 있다.

끄적 끄적

-> 최대값을 찾는 것이므로 무조건 마지막항이 값이라고 생각하면 안된다.
=> 위 그림에서 결과는
dp 표는 1 / 1 / 2 / 3 / 2 / 1 / 4 / 2 로 구성되고, 최대값은 4이다.

점화식

: d[index] : index 까지 오는데 가장 긴 수열의 길이 값

d[7] : 9가 마지막 항이면서 여기까지 오는데 가장 긴 수열의 길이를 뜻한다.

소스코드 1번

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



//5를 만들수 있는 연속 수열 만들기
int main()
{
	vector<int>v = { 5,3,7,8,6,2,9,4 };
	vector<int>dp(v.size(), 1);

	//1 1 1 1 1 1 1 1 1
	//1 1 
	//1 1 2 
	//1 1 2 3

	for (int i = 1; i < v.size(); i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] < v[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}



}

소스코드 2번

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


//위에서 부터 나오게 하자. 
int main(void) 
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	
	int n;
	cin >> n;

	vector<int >v(n);
	vector<int>dp(n, 1);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	dp[0] = 1;

	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (v[j] < v[i])
			{
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << dp[i] << " ";
	}

	cout << endl;

	int max_Value = -1;
	for (int i = 0; i < n; i++)
	{
		max_Value = max(dp[i], max_Value);
	}

	cout << "최대 길이는 "<< max_Value << endl;


}

이코테 병사배치하기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;




int main()
{
	//전투력이 높은 병사가 앞으로 오도록 해야한다. 내림차순으로 
	//lis 문제이다. 

	int n;
	cin >> n;
	vector<int>v(n, 0);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	//4,2,5,8,4,11,15
//dp :1 1 2 3 2  4 5  
	//4,5,8,11,15

	reverse(v.begin(), v.end());

	vector<int>dp(n, 1);

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[j] <  v[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (max < dp[i])
			max = dp[i];
	}
	cout << n - max;

}