[백준] 11055, 12015번 C++: 최장 증가 부분 수열(LIS) 알고리즘

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

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

 

 

11055번

이 문제는 가장 큰 증가 수열로

LIS를 이용하되, 살짝 다른 기법을 사용합니다.

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

int main() {
	int N;
	cin >> N;
	int A[1000] = { 0, };
	int dy[1000];
	int sum[1000];
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		dy[i] = 1; sum[i] = A[i];
	}

	for (int i = 0; i < N; i++) {
		vector<int> v(1);
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j] ) {
				dy[i] = dy[j] + 1;
		
				v.push_back(sum[j]);
			}
		}
		sum[i] += *max_element(v.begin(), v.end());
	}

	cout << *max_element(sum, sum + N);
}

 

 

사실 코드를 볼 때는 이해가 어렵지만 테이블을 통해 이해를 쉽게 할 수 있습니다.

dp는 수열의 길이를 나타내고 sum은 수열의 합을 나타냅니다.

해당 테이블은 최종 테이블이지만, 과정을 나타내보면 아래와 같습니다.

 

i = 0 (A[0] = 1)

• 앞에 원소 없음.
• dp[0] = 1, sum[0] = 1

---

i = 1 (A[1] = 100)

• j = 0 (A[0] = 1), A[1] > A[0]
• dp[1] < dp[0] + 1 → 1 < 1 + 1 → ✔️ 갱신
• dp[1] = 2, sum[1] = A[1] + sum[0] = 100 + 1 = 101

---

i = 2 (A[2] = 2)

• j = 0 (A[0] = 1), A[2] > A[0]
• dp[2] < dp[0] + 1 → 1 < 1 + 1 → ✔️ 갱신
• dp[2] = 2, sum[2] = A[2] + sum[0] = 2 + 1 = 3
• j = 1 (A[1] = 100), A[2] < A[1] → ❌

---

i = 3 (A[3] = 50)

• j = 0 (A[0] = 1), A[3] > A[0]
  → dp[3] < dp[0] + 1 → 1 < 1 + 1 → ✔️
  → dp[3] = 2, sum[3] = 50 + 1 = 51
• j = 1 (A[1] = 100), A[3] < A[1] → ❌
• j = 2 (A[2] = 2), A[3] > A[2]
  → dp[3] < dp[2] + 1 → 2 < 2 + 1 → ✔️
  → dp[3] = 3, sum[3] = 50 + sum[2] = 50 + 3 = 53

---

i = 4 (A[4] = 60)

• j = 0 (A[0] = 1), A[4] > A[0]
  → dp[4] < dp[0] + 1 → ✔️
  → dp[4] = 2, sum[4] = 60 + 1 = 61
• j = 1 (A[1] = 100), A[4] < A[1] → ❌
• j = 2 (A[2] = 2), A[4] > A[2]
  → dp[4] < dp[2] + 1 → ✔️
  → dp[4] = 3, sum[4] = 60 + sum[2] = 60 + 3 = 63
• j = 3 (A[3] = 50), A[4] > A[3]
  → dp[4] < dp[3] + 1 → ✔️
  → dp[4] = 4, sum[4] = 60 + sum[3] = 60 + 53 = 113

---

i = 5 (A[5] = 3)

• j = 0 (A[0] = 1), A[5] > A[0]
  → dp[5] < dp[0] + 1 → ✔️
  → dp[5] = 2, sum[5] = 3 + 1 = 4
• j = 1 (A[1] = 100), A[5] < A[1] → ❌
• j = 2 (A[2] = 2), A[5] > A[2]
  → dp[5] < dp[2] + 1 → ✔️
  → dp[5] = 3, sum[5] = 3 + sum[2] = 3 + 3 = 6
• j = 3 (A[3] = 50), A[5] < A[3] → ❌
• j = 4 (A[4] = 60), A[5] < A[4] → ❌

---

i = 6 (A[6] = 5)

• j = 0 (A[0] = 1), A[6] > A[0]
  → dp[6] < dp[0] + 1 → ✔️
  → dp[6] = 2, sum[6] = 5 + 1 = 6
• j = 1 (A[1] = 100), A[6] < A[1] → ❌
• j = 2 (A[2] = 2), A[6] > A[2]
  → dp[6] < dp[2] + 1 → ✔️
  → dp[6] = 3, sum[6] = 5 + sum[2] = 5 + 3 = 8
• j = 3 (A[3] = 50), A[6] < A[3] → ❌
• j = 4 (A[4] = 60), A[6] < A[4] → ❌
• j = 5 (A[5] = 3), A[6] > A[5]
  → dp[6] < dp[5] + 1 → ✔️
  → dp[6] = 4, sum[6] = 5 + sum[5] = 5 + 6 = 11

---

i = 7 (A[7] = 6)

• j = 0 (A[0] = 1), A[7] > A[0] → ✔️
  → dp[7] = 2, sum[7] = 6 + 1 = 7
• j = 2 (A[2] = 2), A[7] > A[2] → ✔️
  → dp[7] < dp[2] + 1 → ✔️
  → dp[7] = 3, sum[7] = 6 + 3 = 9
• j = 5 (A[5] = 3), A[7] > A[5] → ✔️
  → dp[7] < dp[5] + 1 → ✔️
  → dp[7] = 4, sum[7] = 6 + 6 = 12
• j = 6 (A[6] = 5), A[7] > A[6] → ✔️
  → dp[7] < dp[6] + 1 → ✔️
  → dp[7] = 5, sum[7] = 6 + 11 = 17

---

i = 8 (A[8] = 7)

비슷한 방식으로 계속 업데이트!

---

i = 9 (A[9] = 8)

비슷하게 업데이트!

즉, i 번째 인덱스를 마지막으로

0번 ~ i-1번 부터 i번까지의 수열의 합을

계속해서 업데이트 하는 식입니다.

 

 

12015번

이 문제는 N의 크기가 10^6(백만)으로

O(N^2) 방식으로는 매우 오래 걸립니다.

그래서 N log N 정도로 해야 하는데,

이때 이분탐색을 이용하여

해결할 수 있습니다.

 

백준에 있는 예시보다 아래 예시가 더

다양한 케이스를 볼 수 있어서

A = {20, 10, 30, 40, 20, 50}

을 예시로 들어보겠습니다.

 

여기서, 30에서 20으로 바뀜에도길이가 4인 것에 의문을 느낄 수 있습니다.

 

여기서 중요한 것은, 20보다는 길이에 초점을 맞춰야 합니다.

 

그러면 20으로 바뀐 이유는 무엇인가 살펴 봤을 때 다음의 예시를 들 수 있습니다.

 

A = { 20, 10, 30, 60, 20, 30, 40, 50 }이때의 경우 30의 자리가 20으로 교체되고60의 자리가 30으로 교체되며

 

lis = { 10, 20, 30, 40, 50 }으로나오게 됩니다.

 

즉, 여기서 중요한 것은 이분탐색을 통해다음 요소가 만약 lis의 마지막 요소보다 값이 작다면

lis 중 어디 인덱스에 들어갈 수 있는지를 판단하는 것입니다.

 

 

 

#include <iostream>

using namespace std;


int arr[1000001];
int lis[1000001];

int BinarySearch(int left, int right, int target)
{
	int mid;

	while (left < right)
	{
		mid = (left + right) / 2;
		if (lis[mid] < target)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}
	return right;
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
		lis[i] = 0;
	}

	int length = 1;

	lis[1] = arr[1];
	for (int i = 1; i <= N; i++)
	{
		if (lis[length] < arr[i])
		{
			lis[length + 1] = arr[i];
			length += 1;
		}
		else
		{
			int idx = BinarySearch(1, length, arr[i]);
			lis[idx] = arr[i];
		}
	}

	cout << length;
}