백준 Gold 2 가장 긴 증가하는 부분 수열 2

가장 긴 증가하는 부분 수열 2 (백준 Gold 2)

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

수열이 주어졌을 때
가장 긴 증가하는 부분 수열의 길이를 구하는 문제

풀이 방법

• 먼저 LIS용 vector를 하나 준비하기
  (ret)
  

• 해당 배열에 수열을 ‘하나씩’ 집어넣으며 진행
  

• 수열의 현재값이 배열의 가장 뒤값 보다 크다면
  그대로 배열에 집어넣기
  

• 만약 그렇지 않다면
  ‘현재의 배열’ 내부에서
  ‘가장 이 값과 가까운’ 값으로 교체
  

  • 이렇게 교체하여도 ret는 ‘오름차순’을 유지함
    
  • 교체하는 위치는 현재의 ‘LIS’ 중
    대체 가능한 값
    

ex)

10 30 20 40 에서

{10 , 30} 에서 다음 20을
{10, 20} 으로 교체함으로서
둘다 길이는 2이지만

다음에 나올 40을 통해
{10,30,40}
{10,20,40} 자체는 길이가 같아짐

• 순서는 유지하되
  ‘대체 가능한’ 값으로 교체하는 방식
  

• ‘오름차순’이 유지되며
  항상 대체 가능한 부분만이 대체 되기에
  ‘결과’와 ‘길이’는 같음
  

• 다만 LIS 자체를 구하는 방식이라면
  다른 방식을 고려해야 함
  

  • 보통 Idx를 별도로 저장하는 역추적을 고려
    

제출 코드

#include <iostream>
#include <vector>

using namespace std;

int FindLikeValue(vector<int>& arr, int v)
{
	int left = 0;
	int right = arr.size() - 1;

	while (left < right)
	{
		int mid = (left + right) / 2;

		if (arr[mid] == v)
		{
			return mid;
		}

		if (arr[mid] > v)
			right = mid;
		else
			left = mid + 1;
	}

	return right;
}

int main(void)
{
	/*
		lcs 배열을 만들되
		하나씩 증가하면서 제작

		정답 배열
		n번째가 n-1 번째 보다 크다면
		정답 배열에 추가

		아니라면
		정답 배열 내부를 이분 탐색하여
		가장 가까우면서 큰 녀석과 교체
	*/

	int n;
	cin >> n;

	vector<int> arr(n);

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	vector<int> ret;
	ret.push_back(arr[0]);

	for (int i = 1; i < n; i++)
	{
		if (arr[i] > ret.back())
		{
			ret.push_back(arr[i]);
		}
		else
		{
			// 이진 탐색으로 가장 비슷한 값에 대입
			int idx = FindLikeValue(ret, arr[i]);
			ret[idx] = arr[i];
		}
	}

	cout << ret.size();

	return 0;
}

결과

‘이분탐색’에 너무 매몰되어서 조언을 듣기 전까지는
풀지 못하였다

• dp로 풀어야 하는 문제인가 싶었다
  
  • dp로도 풀 수 있으나 그 경우는 O(N^2)가 됨
    
  • 그래도 역추적을 추가하는 경우는 dp가 조금 더 로직이 쉬울 수 있음
    (직관적)
    
• 때로는 문제의 타입이 곧 문제의 정답을 구하는 방식이 아니라
  하나의 ‘로직’으로서 기능한다는 것을 종종 잊을때가 있다