최근 : 예시만 보고 판단할 경우 틀림.
-> 이 코드로 하면 위 그림의 입력은 통과함 .
하지만 반례가 있음.
10 20 1 2 3 4 5 30
이 있다고 한다면. 내 코드를 틀림.
-> 여러가지 반례, 경위의 수 에 대해 생각을 해야 함.
최근 : 어떻게 만들까?
1) 일단 2중 포문을 사용함.
왜 이중 포문임?
예를 들어 나의 인덱스 6번의 원소 가 0,1번보다 값이 작지만,
2, 3,4,5 보다 클 경우, -> 6번 원소가 0,1번보다 카운팅 갯수가
클 수가 있음을 생각해야 함.
그래서 어떻게 할 건데
타겟으로 잡은 인덱스를 기준으로 해서, 이전의 인덱스의 원소값을 비교해서 , 새로운 변수에 카운팅을 해야함.
2) max 값이 필요함!
카운팅을 어떻게 할 것인가에 대해서
-
일단 이렇게 만들었음. : v2는 카운팅을 기록하는 배열임.
-
it문 안을 이렇게 하게 되면,,,
5번 인덱스의 카운팅이 3이고, 6번인덱스의 카운팅이 0인데,
7번 나의 원소가 5번과 6번보다 모두 크다고 할 경우,
6번 카운팅 + 1을 하게됨.
-> 최대 증가이므로 잘못됨.
max 변수를 기록해나가야 함을 확인할 수 있는 설명임. -
잘못된 부분
-> 이대로 해도 되지만, 오류 발생함.
: 내가 이렇게 한 의도는.. 원소값들을 비교하면서 하면 되지 않을까?
생각을 해서임....
=> 그리고 , max_element를 사용해서 그런듯함?
-> 문제의 의도가 가장 큰 카운팅을 구하는 것이므로 ,
max 와 비교할 대상을 카운팅 배열과 대결 하도록 하자.
이게 왜 가능한 것인가에 대해서
-> 생각을 해보면? 카운팅 배열이 의미하는 것은 앞에 있는 원소 비교했을 때,
가장 긴 수열이라는 것을 의미하고 있기 때문임.
언제 사용할까
: 정해진 컨테이너의 순서를 해치지 않으면서, 오름차순으로 가장 길게 나열할 수 있는 집합을 만드려고 할때 사용한다.
- [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;
}
