[BOJ/백준 2352/C++] 반도체 설계

https://www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

[문제 요약]

- 예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다.

- 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다.

- n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내시오.

 

 

[문제 조건]

- 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 

- 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

이 문제는 전에 한번 비슷한 문제를 푼 경험이 있어서 아이디어를 잡는데 오래 걸리지는 않았다.

 

문제의 핵심은 선이 꼬이지 않게 선택하는 것이다. 선이 꼬이지 않으려면 선택한 오른쪽 포트들의 번호가 감소하지 않고 증가하면 된다.

 

이런 유형의 문제를 LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)라고 한다. 

 

그렇다면 최장 증가 부분 수열이란 무엇인가?

• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 큰 수열이면서, 그 길이가 가장 긴 부분 수열을 의미한다.
• 예를 들어 {4, 2, 6, 3, 1, 5} 가 있을 때 , LIS는 {2, 3, 5}가 된다.

LIS는 푸는 방법이 대표적으로 2가지 방식이 있다. 하나는 O(N^2) , 하나는 O(N log N)의 시간복잡도를 가진다.

 

O(N^2)

- DP를 이용한 방법이다. 

- dt[] 배열은 원소를 가지고 있는 배열, dp[] 배열은 i번째까지 LIS의 길이를 의미하는 배열이다.

- dt[]배열의 원소를 하나씩 확인하면서 진행한다.

- k번째 원소보다 인덱스가 작은 원소들과 비교하면서 k번째 원소의 값보다 작은 원소가 있을 경우(h번째) dp 배열을 갱신한다.

 

갱신하는 기준은 다음과 같다.

• h번째 원소로 끝나는 LIS에 k번째 원소를 추가했을 때의 LIS의 길이
• 기존의 LIS 길이

둘 중 큰 값으로 갱신이 이루어진다.

 

기존의 dp배열은 모두 1로 초기화 되어있다.

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

 

하지만 이 방법은 주어진 문제에서는 풀리지 않는 방법이다. 왜냐하면 n의 크기가 최대 4만이라 시간이 오래걸리기 때문이다.

 

 

O(N log N) - 길이

이분탐색을 이용한 방법이다. 

 

이 방법의 핵심은 LIS를 만들 때 LIS의 마지막 원소를 작게 만들어서 더 긴 LIS를 만들도록 하는 것이다.

 

예를 들어 {1, 2, 3, 4, 9, 8, 7} 이 있다고 할 때 {1, 2, 3, 9}도 LIS를 만족 시키지만 {1, 2, 3, 7}도 LIS를 만족한다. 

- LIS는 정답이 한 개가 아닐 수 있다.

여기서 전자도 LIS에 해당은 되지만 만약 뒤에 원소가 더 있다면 후자의 경우가 나중에 더 긴 LIS를 만들기에는 유용하다.

이 아이디어를 이용해 시간을 줄일 수 있다.

 

문제에서 주어진 예제를 가지고 한 번 설명해보도록 하겠다. 방법은 아래와 같다.

• dt배열의 원소를 차례대록 확인하면서 , LIS배열에 하나씩 추가한다.
• 추가할때 이분 탐색을 이용하여 원소의 값보다 큰 값이 나타나는 처음 위치에 교환해준다.  
• 최종적으로 남은 LIS의 길이가 주어진 dt배열로 만들 수 있는 LIS의 최대 길이이다.

처음에는 아무것도 없으니 그냥 추가해준다.

 

2를 LIS 배열에 추가할려고 확인해봤더니 2보다 큰 값이 나타나는 처음위치의 인덱스는 0이 였을 것이다. 이때 4대신 2를 넣어준다.

 

원소를 추가할때 LIS의 마지막 원소보다 넣을 원소값이 더 크면 그냥 맨 뒤에 넣어주면 된다. 왜냐하면 어차피 이분탐색을 통해 확인해봤자 모든 값들이 넣을 원소의 값보다는 작을 것이다.

 

3을 LIS에 배열에 추가할려고 확인했더니 3보다 처음으로 큰 값이 나타나는 곳의 인덱스는 1이다. 이때 6대신 3을 넣어준다.

1을 LIS에 배열에 추가할려고 확인했더니 1보다 처음으로 큰 값이 나타나는 곳의 인덱스는 0이다. 이때 2대신 1을 넣어준다.

마지막으로 5을 넣어주면 된다.

 

여기서 LIS배열의 길이가 최종적으로 주어진 배열로 만들 수 있는 LIS의 길이가 된다.

 

근데 여기서 매우매우 중요한 점이 하나 있다.

 

위 방법을 통해 만들어진 LIS배열은 실제로 만들 수 있는 LIS가 아니다. 여기까지 방법으로는 길이만 구할 수 있지 정확한 LIS를 구할 수는 없다. 구하기 위해서는 추가적인 작업이 더 필요하다.

 

 

O(N log N) - 길이 & 수열

만약 LIS까지 구하고 싶다면 아래의 방법을 추가적으로 해주면된다.

• 위의 LIS배열에 했던 작업에다가 각 원소들이 LIS배열에 들어갈때의 인덱스를 저장해둔다.
• 이 인덱스 배열의 뒤에서부터  LIS의 길이를 감소시켜가면 , 처음으로해당 길이의 index가 나오는 원소만 뽑아낸다

위의 과정 중간에 index까지 추가하면 아래와 같은 배열이 완성된다.

1번원소(index=0)인 4는 LIS배열에 1번 위치(index = 0)에 들어갔다.

2번원소(index=1)인 2는 LIS배열에 1번 위치(index = 0)에 들어갔다.

3번원소(index=2)인 6는 LIS배열에 2번 위치(index = 1)에 들어갔다.

4번원소(index=3)인 3는 LIS배열에 2번 위치(index = 1)에 들어갔다.

5번원소(index=4)인 1는 LIS배열에 1번 위치(index = 0)에 들어갔다.

6번원소(index=5)인 5는 LIS배열에 4번 위치(index = 2)에 들어갔다.

 

여기서 뒤에서 부터 확인하면된다. LIS의길이가 3이였으니 처음에 3이 나오는 원소는 5다.

그 다음 2가 처음에 나오는 원소는 3이다.

다음 1이 처음에 나오는 원소는 2가 된다.

 

따라서 2, 3, 5가 우리가 원하는 LIS가 된다.

 

 

 

 

우리가 처음에 풀려고했던 문제 2352번 문제는 길이만 구하면 되는 문제라 수열까지는 구할 필요는 없지만, 알아두면 언젠가 썩먹을 일이 있을 것이다. 수열까지 구하는 문제는 아래 링크로 남겨두겠다.

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

 

[길이만 구하는 소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N;
vector<int> dt;
vector<int> ans_list;

int binary(int start, int end, int value)
{
	while (start < end)
	{
		int mid = (start + end) / 2;
		if (ans_list[mid] < value) start = mid + 1;
		else end = mid;
	}
	return end;
}

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

	cin >> N;
	dt.resize(N + 1);

	for (int i = 1; i <= N; i++) cin >> dt[i];

	ans_list.push_back(dt[1]);

	for (int i = 2; i <= N; i++)
	{
		if (dt[i] > ans_list[ans_list.size() - 1]) ans_list.push_back(dt[i]);
		else
		{
			int pos = binary(0, ans_list.size() - 1, dt[i]);
			ans_list[pos] = dt[i];
		}
	}

	cout << ans_list.size();
}

 

[길이와 수열 모두 구하는 소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

using namespace std;

int N;
vector<int> dt;
vector<int> ans_list;
vector<int> index;

int binary(int start, int end, int value)
{
	while (start < end)
	{
		int mid = (start + end) / 2;
		if (ans_list[mid] < value) start = mid + 1;
		else end = mid;
	}
	return end;
}

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

	cin >> N;
	dt.resize(N + 1);
	index.resize(N + 1);

	for (int i = 1; i <= N; i++) cin >> dt[i];

	ans_list.push_back(dt[1]);
	index[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		if (dt[i] > ans_list[ans_list.size() - 1])
		{
			ans_list.push_back(dt[i]);
			index[i] = ans_list.size();
		}
		else
		{
			int pos = binary(0, ans_list.size() - 1, dt[i]);
			ans_list[pos] = dt[i];
			index[i] = pos+1;
		}
	}
	vector<int> ans;
	int tmp = ans_list.size();
	cout << tmp << "\n";
	for (int i = N; i >= 1; i--)
	{
		if (index[i] == tmp)
		{
			ans.push_back(dt[i]);
			tmp--;
		}
	}
	for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
}

 

추가적으로 우리가 LIS배열에 원소를 집어넣을 때 직접 이분탐색 코드를 작성하지 않고 lower_bound함수를 이용하여 구할수도 있다. 참고하시길

 

[2352번]

 

- N^2를 이용하면 시간초과가 발생한다.

 

 

[14003번]

 

굳