(백준/C++) 가장 긴 증가하는 부분 수열 1(11053), 2(12015), 3(12738), 4(14002), 5(14003) 모두 풀기

12738오늘은 가장 긴 증가하는 부분 수열 1, 2, 3, 4, 5를 모두 풀어볼겁니다. 

이 문제들을 다 풀었다면 자연스럽게 11055번 가장 큰 증가 부분 수열과 11054번 가장 긴 바이토닉 부분 수열은 쉽게 풀수 있을겁니다. 

저는 단계별로 풀어보기에서 이분 탐색을 풀면서 연관된 문제 그냥 다 풀어보자 하는 마음으로 풀어보았고, 많은 블로그도 보고 질문 게시판의 도움도 받으면서 풀었습니다. 

자 이제 그럼 풀어봅시다. 

---

 

❗문제❗

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

11053번 -  가장 긴 증가하는 부분 수열 1 ( https://www.acmicpc.net/problem/11053 )
🔹입력🔹
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
🔹출력🔹
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

12015번 - 가장 긴 증가하는 부분 수열 2 ( https://www.acmicpc.net/problem/12015 )
🔹입력🔹
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
🔹출력🔹
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

12738번 - 가장 긴 증가하는 부분 수열 3  ( https://www.acmicpc.net/problem/12738 )
🔹입력🔹
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
🔹출력🔹
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

14002번 - 가장 긴 증가하는 부분 수열 4  ( https://www.acmicpc.net/problem/14002 )
🔹입력🔹
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
🔹출력🔹
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

14003번 - 가장 긴 증가하는 부분 수열 5  ( https://www.acmicpc.net/problem/ 14003 )
🔹입력🔹
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
🔹출력🔹
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

5문제 모두 같은 문제가 주어지지만 문제의 조건이 조금씩 다르고 여기서 사용하는 알고리즘은 DP와 이분탐색입니다.

빨간색은 DP를 파란색은 BS를 사용할겁니다. 먼저 어디서 알고리즘 차이가 오는지 문제를 풀면서 알아봅시다. 

일단 DP문제 부터 풀어봅시다. 

---

 

(1). DP 풀이 (11053번, 14002번)

ex)  A = {10, 20, 10, 30, 20, 50}  

1. 목표: DP[idx] 현재 i 까지 증가하는 수열의 개수를 넣는다.  DP = {1, 2, 1, 3, 2, 4}
2. 증가할때 이전의 인덱스를 넣어준다. V = {-1, 0, -1, 1, 0, 3} 
3. 완전 탐색하면서 가장 큰 DP[idx]를 찾는다. → 11053번의 답
4. 가장 큰 DP[idx]의 idx부터 V를 탐색하며 -1이 나올때까지 탐색하여 vector에 넣어준다.
5. vector를 reverse를 하거나 하나씩 빼(back) 출력한다.  → 14002번의 답

 

👌 14002번  코드👌 

11053번은 size만 출력하면 되므로 코드 생략했습니다.

#include <iostream>
#include <memory.h>
#include <vector>
using namespace std;
int A[1000], DP[1000], V[1000];

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
	}
	int maxCount = 1;
	int index = 0;
	DP[0] = 1;

	memset(V, -1, sizeof(V));

	for (int i = 1; i < N; ++i) {
		DP[i] = 1;
		for (int j = 0; j < i; ++j)
		{
			if ((A[j] < A[i]) && (DP[i] < DP[j] + 1))
			{
				DP[i] = DP[i] + 1;
				V[i] = j;
				if (maxCount < DP[i])
				{
					maxCount = DP[i];
					index = i;
				}
			}
		}
	}

	cout << maxCount << "\n";
	vector<int> vec;
	while(V[index] != -1)
	{
		vec.push_back(A[index]);
		index = V[index]; 
    }
	vec.push_back(A[index]);

	for (int i = vec.size()-1; i >=0; --i)
	{
		cout << vec[i] << " ";
	}
	return 0;
}

---

 

(2). 이분탐색 풀이 (12015번, 12738번, 14003번)

저는 이분탐색 알고리즘으로 푸는 아이디어는 전혀 떠올리지 못했습니다. 많은 블로그 풀이와 질문게시판을 보고 이해하고 풀었습니다.  제가 이해한 내용을 그림으로 표현해보았습니다.  이해하는 대에 도움이 되었으면 좋겠습니다.😊 코드와 같은 변수이름을 가지고 있으니 코드 보면서 이해하시길..

ex)  A = {10, 20, 5, 30, 15, 50}

1. vec 안에 첫번째 A[0]을 넣어준다 (A와 비교를 위한)
2. vec.back() < A[i]가 true이면 vec에 현재 A[i]를 넣어주고(증가 수열이기때문에) 감소하면 개수에 변함이 없도록 치환해준다. 
3. 이때 치환할 위치를 찾기 위해서 이분탐색을 사용한다. (이분탐색을 할 수 있는 이유는 vec는 오른차순으로 정렬이 되어있기때문이다.여기서 만약 왜 정렬되어 있어서 이분탐색을 할수 있는지 모르겠다면 이분탐색을 다시 공부하고 오자.유투브만 봐도 잘 나옴.)
4.  2번 3번 할 때 v 배열에 현재 idx에서 A[idx]가 vec[i] 중 어디 i에 들어갈지 넣어준다.(vec에 존재하는 실제 위치 14003번의  출력값이 된다.)
5. vec의 크기는 12015번, 12738번의 출력값이 된다.

 

 

👌 14003번 👌

12015번과 12738번은 size만 출력하면 되므로 코드 생략했습니다.

#include <iostream>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
int A[1000000], V[1000000];

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;

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

	vector<int> vec; 
	vec.push_back(A[0]);
    memset(V, -1, sizeof(V));
	V[0] = 0;
	for (int i = 1; i < N; ++i) {
		if (vec.back() < A[i])
		{
			vec.push_back(A[i]);
			V[i] = vec.size() - 1;
		}
		else
		{
			int start = 0; 
			int end = vec.size() - 1;
			int mid = end;

			while (start < end)
			{
				mid = (start + end) / 2; // (start = 0 + end = 3)  2 = 1 

				if (vec[mid] < A[i]) // ex) vec[] = 10,(*)15, 18, 25, 30 <--- push (20)
				{
					start = mid + 1;
				}
				else // ex) vec[] = 10, 15, 18,(*)25 30 <--- push (20)
				{
					end = mid;
				}

			}
            vec[end] = A[i];
			V[i] = end;
		}
	}
	//=======================================//
	vector<int> _result;
	int index = vec.size() - 1;

	for (int i = N; i >= 0; --i)
	{
		if (V[i] == index)
		{
			_result.push_back(A[i]);
			--index;
		}
	}
	//=======================================//
	cout << vec.size() << "\n";

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

	for (auto& res : _result)
	{
		cout << res << " ";
	}
	return 0;
}

 

바이용