백준 12015 c++ "가장 긴 증가하는 부분 수열 2" -PlusUltraCode-

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

[필자 코드]

먼저 LIS 를 알아야 된다.

*가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)**은 주어진 수열에서 일부 숫자들을 골라내어, 원래 순서를 유지한 채로 증가하는 형태로 만들 수 있는 가장 긴 부분 수열을 찾는 문제입니다.

• 예를 들어, 수열이 [10, 20, 10, 30, 20, 50]라면, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]입니다.
• 중요한 점은, 수열 내 숫자의 순서를 바꾸지 않는다는 것입니다. 따라서 단순히 숫자를 크기순으로 나열하는 문제가 아닙니다.

위 코드는 LIS를 효율적으로 계산하기 위해 **이진 탐색 (Binary Search)**를 활용한 방법을 사용하고 있습니다.

 

필자는 이분탐색 알고리즘 lower_bound 를 이용하여 이 문제를 해결했다. 

 

아래는 소스 코드 해설이다.

 

• 입력 처리
  프로그램은 먼저 정수 N을 입력받아 배열의 크기를 설정합니다. 이후 N개의 정수를 배열 Arr에 저장합니다. 이 단계에서는 입력 데이터만 처리하며, 계산은 아직 이루어지지 않습니다.
• GameStart 함수
  이 함수는 LIS를 구하는 핵심 알고리즘을 담당합니다. 입력받은 배열 Arr를 순차적으로 탐색하며 다음과 같은 과정을 수행합니다:
  • 현재 값 num이 binaryArr의 마지막 값보다 작거나 같다면, binaryArr에서 num이 들어갈 위치를 **이진 탐색 (lower_bound)**으로 찾아 해당 값을 교체합니다.
    이 작업은 binaryArr를 항상 증가하는 순서로 유지하는 역할을 합니다.
  • 그렇지 않은 경우, 즉 num이 binaryArr의 마지막 값보다 크다면, binaryArr의 끝에 추가합니다.
    이는 수열이 증가할 때 새로운 값을 추가하여 LIS를 확장하는 동작입니다.
• 결과 출력
  메인 함수에서 GameStart를 실행한 뒤, binaryArr의 크기를 출력합니다. 이 크기는 배열 Arr에서 찾은 LIS의 길이를 의미합니다.
  결과적으로, 이 프로그램은 LIS를 효율적으로 계산하기 위해 이진 탐색과 동적 배열을 활용하는 방식으로 동작합니다.

 

[소스 코드]

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

using namespace std;

vector<int> Arr;
vector<int> binaryArr;
int N;

void Input() {
	cin >> N;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> Arr[i];
	}
}

void GameStart() {
	for (int i = 0; i < N; i++) {
		int num = Arr[i];

		if (i != 0 && num <= binaryArr.back()) {
			auto it = lower_bound(binaryArr.begin(), binaryArr.end(), num);
			*it = num;
			continue;
		}
		binaryArr.push_back(num);
	}
}

int main(void) {
	Input();
	GameStart();
	cout << binaryArr.size();
}