백준 11053 가장 긴 증가하는 부분 수열 LIS+DP

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

 

문제:

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하기

e.g. 수열 A = {10, 20, 10, 30, 20, 50} , 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4

 

입력

첫째 줄 수열 A의 크기 N (1 ≤ N ≤ 1,000)

둘째 줄 수열 A를 이루고 있는 Ai (1 ≤ Ai ≤ 1,000)

 

출력

수열 A의 가장 긴 증가하는 부분 수열의 길이

 

---

LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘 :

주어진 수열에서 일부 원소를 선택하여 순서를 유지하면서 가장 긴 증가하는 부분 수열

동적 계획법(DP, Dynamic Programming) 을 활용하여 구현

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

int n;
vector<int> Nums;

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

	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		Nums.push_back(a);
	}
	vector<int>IncreaseNums(n, 1);
	
	//for (auto a : Nums) cout << a<<" ";


	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++) 
		{
			if (Nums[j] < Nums[i])
			{
				// 이전 LIS 길이에 1 추가
				IncreaseNums[i] = max(IncreaseNums[i], IncreaseNums[j]+1);
			}
		}
	}

	// 가장 긴 증가 부분 수열의 길이 찾기
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		result = max(result, IncreaseNums[i]);
	}

	cout << result << "\n";
	return 0;
}

⚡ 시간 복잡도를 줄이는 방법

• 위 알고리즘은 O(N2)O(N^2)O(N2) 시간 복잡도를 가짐
• 이진 탐색(Binary Search) + DP 활용 시 O(Nlog⁡N)O(N \log N)O(NlogN) 가능
• 이를 위해 lower_bound() 를 이용한 이분 탐색 + vector 사용 (LIS의 실제 수열 구성 X, 길이만 구함)

 

🔹 중간 과정

i Nums[i] 가능한 j 값 Nums[j] 조건 만족 IncreaseNums 업데이트

1	20	j=0 (10)	✅ (10 < 20)	IncreaseNums[1] = 2
2	10	j=0,1	❌ (10보다 작은 값 없음)	IncreaseNums[2] = 1
3	30	j=0,1,2	✅ (10, 20 < 30)	IncreaseNums[3] = 3
4	20	j=0,1,2,3	✅ (10 < 20)	IncreaseNums[4] = 2
5	50	j=0,1,2,3,4	✅ (10, 20, 30 < 50)	IncreaseNums[5] = 4

---

🔹 최종 IncreaseNums 배열

Index:   0  1  2  3  4  5
Nums:   [10 20 10 30 20 50]
DP:     [1  2  1  3  2  4]

---

📌 IncreaseNums 배열 업데이트 과정 자세한 설명

---

✅ 초기값 설정

vector<int> IncreaseNums(n, 1);

• 처음에는 모든 원소의 LIS 길이를 1로 초기화
  → 각 원소는 최소 자기 자신 하나로 LIS를 형성할 수 있음.

초기 상태

IncreaseNums = [1, 1, 1, 1, 1, 1]

---

1️⃣ i = 1, Nums[i] = 20

• j = 0, Nums[0] = 10
• Nums[0] < Nums[1] (✅ 증가 수열 가능)
• IncreaseNums[1] = max(IncreaseNums[1], IncreaseNums[0] + 1)

  IncreaseNums[1] = max(1, 1 + 1) = 2
  

현재 상태

IncreaseNums = [1, 2, 1, 1, 1, 1]

---

2️⃣ i = 2, Nums[i] = 10

• j = 0, Nums[0] = 10 (❌ 증가 아님)
• j = 1, Nums[1] = 20 (❌ 증가 아님)
• IncreaseNums[2]는 변함 없음

현재 상태

IncreaseNums = [1, 2, 1, 1, 1, 1]

---

3️⃣ i = 3, Nums[i] = 30

• j = 0, Nums[0] = 10

  IncreaseNums[3] = max(1, 1 + 1) = 2
  

• j = 1, Nums[1] = 20

  IncreaseNums[3] = max(2, 2 + 1) = 3
  

• j = 2, Nums[2] = 10

  IncreaseNums[3] = max(3, 1 + 1) = 3
  

현재 상태

IncreaseNums = [1, 2, 1, 3, 1, 1]

---

4️⃣ i = 4, Nums[i] = 20

• j = 0, Nums[0] = 10

  IncreaseNums[4] = max(1, 1 + 1) = 2
  

• j = 1, Nums[1] = 20 (❌ 증가 아님)
• j = 2, Nums[2] = 10

  IncreaseNums[4] = max(2, 1 + 1) = 2
  

• j = 3, Nums[3] = 30 (❌ 증가 아님)

현재 상태

IncreaseNums = [1, 2, 1, 3, 2, 1]

---

5️⃣ i = 5, Nums[i] = 50

• j = 0, Nums[0] = 10

  IncreaseNums[5] = max(1, 1 + 1) = 2
  

• j = 1, Nums[1] = 20

  IncreaseNums[5] = max(2, 2 + 1) = 3
  

• j = 2, Nums[2] = 10

  IncreaseNums[5] = max(3, 1 + 1) = 3
  

• j = 3, Nums[3] = 30

  IncreaseNums[5] = max(3, 3 + 1) = 4
  

• j = 4, Nums[4] = 20

  IncreaseNums[5] = max(4, 2 + 1) = 4
  

최종 상태

IncreaseNums = [1, 2, 1, 3, 2, 4]

---

🎯 최종 결과

LIS의 길이 = 4

LIS 경로: {10 → 20 → 30 → 50} 🚀

이해되었어? 더 설명이 필요하면 말해줘! 😃

---

4️⃣ 시간 복잡도

• 이중 반복문으로 인해 O(N2)O(N^2) 시간 복잡도
• N이 크면 (예: N>105N > 10^5) 이분 탐색 활용 (O(N log N))으로 최적화 가능

---

5️⃣ 개선된 LIS 알고리즘 (이분 탐색)

아래 코드는 이진 탐색을 활용하여 LIS를 O(N log N)에 구하는 방법입니다.

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

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

    int n;
    cin >> n;
    
    vector<int> A(n);
    vector<int> lis; // LIS 저장 (이분 탐색 활용)

    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
        auto it = lower_bound(lis.begin(), lis.end(), A[i]);

        if (it == lis.end()) // A[i]가 LIS의 마지막 값보다 크면 추가
        {
            lis.push_back(A[i]);
        }
        else // LIS 내부에서 적절한 위치에 값 교체
        {
            *it = A[i];
        }
    }

    cout << lis.size() << "\n"; // LIS 길이 출력
    return 0;
}

---

6️⃣ 최종 정리

방법 시간 복잡도 특징

DP (O(N^2))	O(N2)O(N^2)	dp[i] 배열을 이용하여 LIS 길이 계산
DP + 이분 탐색 (O(N log N))	O(Nlog⁡N)O(N \log N)	lower_bound() 활용, LIS 길이만 구함

🚀 결론

• O(N^2) 방식은 이해하기 쉽고 구현이 간단하지만 느림
• O(N log N) 방식은 빠르지만 실제 LIS를 구하기 어려움
• 만약 LIS 길이만 필요하다면 O(N log N) 방식 추천! 🎯

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n, lis[1001], len, num;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	fill(lis, lis + 1001, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		auto lowerpos = lower_bound(lis, lis + len, num);

		if (lowerpos == lis+len) len++;
		*lowerpos = num;
		//cout << "*lowerpos : "<< *lowerpos << '\n';
		//cout << "lowerpos : " << lowerpos << endl;
		
		
		for (int j = 0; j < n; j++)
		{
			//cout << lis[j] << " ";
		}
		//cout << "\n";
	}

	cout << len << endl;
	vector<int> result;
	for (int i = 0; i < len; i++)
	{
		result.push_back(lis[i]);
		
	}
	for (int i = 0; i < len; i++)
	{
		cout << result[i] <<" ";
	}

	return 0;
}

 

lower_bound는 → O(log N)

 

• lower_bound()는 이진 탐색을 사용하므로 O(log N)
• lis는 항상 정렬된 상태이므로 lower_bound()를 사용

n개의 숫자를 입력받고 lower_bound()를 호출하는 반복문

따라서 전체 시간 복잡도는:

O(n log⁡ n)