최근 정리

• 예제에서 주어진 예시 말고도, 반례를 미리 만들어 놓고 생각하자.

예시를 통해 생각해야 함.

• 잘못된 코딩.
  나의 예시로는 이렇게 밖에 못함.
  
  -> 문제가 있음. 아래의 예시 입력에는 적용되지 못함.
  

접근 방법.

인덱스 4번의 원소를 기준으로 해서 , 앞에 있는 모든 원소간의 비교를 진행하자.
10 20 1 2 3 4 25 의 경우.
25에 위치한 인덱스의 경우, 카운팅 배열 값이 2번 바뀜..
첫번째 시도 : 1 2 1 1 1 1 3
두번째 시도 : 1 2 1 2 3 4 5
-> 5가 출력

최종 코드

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>


int main()
{
	
	int n;
	cin >> n;
	vector<int>v(n, 0);
	vector<int>cnt(n, 1);

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

	// 10 20 21 1 2 25
	// 1  2   3 1 2 4

	// 10 20 1 2 3 4  25	
	// 1  2  1 2 3 4  3
	// 1 2   1 2 3 4  5

	// 10 20 10 30 20 50
	int res = 0;
	// 이중 포문
	// 각 원소 위치에서 최대 부분수열 카운팅을 나타나게 하자.
	for (int i = 0; i < n; ++i)
	{
		int maxx = 0;
		for (int j = 0; j < i; ++j)
		{
			if (v[i] > v[j] && maxx < cnt[j])
			{			
            	//계속해서 최대값을 갱신함.
				maxx = cnt[j];
			}
		}
        // 맨 마지막에서 최대값인 maxx로 카운팅 배열을 갱신해야 함.
		cnt[i] = maxx + 1;
        // 출력용 최대값을 구함.
		res = max(res, cnt[i]);
	}

	cout << res;
}

LIS

: 그림 그리고 코딩하자!

#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]);
			}
		}
	}

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

	cout << max_Value;


}