백준 2352번은
일반적인 DP코드로는 N^2 시간복잡도가 걸립니다.
왜 N^2인지는 밑의 코드 주석에 작성
알고리즘에서 lower_bound라는 함수를 사용했는데,
대단한 함수는아니고 직접 작성하여도 되는 함수이다.
lower_bound(첫주소, 마지막주소, 찾는 값) return iter or pointer 주소값
매개변수 인자는, STL의 iterator를 넣어도 되고, 배열의 주소값을 넣어도 됩니다.
이 함수는 이미 오름 차순으로 sort된 배열에서 binary search를 하여 찾고자 하는 값이 있는 인덱스(iter or 주소)를 알려주는 함수입니다.
만약 값이 존재하지 않는다면, 찾는값 보다 큰 수 중에서 작은 값을 찾습니다. (2, 5, 8) 에서 4를 찾는다면 idx 1 (5) 반환
모든 수가 찾으려는 값보다 작다면, end()를 반환 합니다.
LIS 알고리즘은 NlongN 복잡도로, 입력받은 순열을 하나씩 순회하며 최장순열 길이를 업데이트 한는 방식입니다.
업데이트 할때 binary search가 사용됩니다.
밑의 LIS함수의 코드 알고리즘을 대~충 읽으시면 설명들어갑니다잉 코드가 매우 짧습니다
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int N;
vector<int> port;
vector<int> dport;
//N^2 알고리즘
// 이미 계산된 값을 발견하는것은 for문안에 한개의 인스트럭션(명령어)으로 생각할 수 있다.
// vector의 N개의 값이 최초 한번씩은 발견되므로 무조건 N번의 dp함수는 for문을 실행시킨다.
// for문이 N - src 번 돌아가므로... N^2 알고리즘이다. 4만개는 풀수 없다...
// 사실상 저 for문을 줄일 수 있을거 같다..
// for문안에 dp(i)들 중에는 분명 같은 수열안에 포함되는 녀석들도 존재할텐데
// 같은 수열안에 포함되고 있는데도 한 번 씩 찾아보고 있다..
// ex) src = 2 일때 dp(3~N) 까지 돌면서 mmax를 갱신하는데
// 사실 dp(3~N)의 dport의 값은 이미 dfs특성상 다 구해져 있을 것이고
// 만약 dp(3~N)이 모두 같은 오름차순 수열에 포함되어있다면
// 사실상 src = 2일때 . 3~N for문을 진짜 모두 다 뒤져볼 필요는 없음에도 살펴보았다..
// dp 배열에 저장하는 결과값 의미를 src부터 시작했을 때가 아닌, src이후 최장 순열중로 바꾸고
// 필요한 데이터 캐시들을 더욱 많이하면 시간은 줄일 수 있을 거 같긴한데
// 최악 알고리즘이 N^2인건 그대로 일거 같긴하다..
// 방법은 결국 LIS이긴하다. dp를 쓰더라도 src이후 최장 순열 값을 LIS식으로 유지해야 가능하다.
// LIS는 본문에서 확인 가능하며, dp방식에서 LIS를 쓰면 탑 다운식이여서 순열 순서가 반대로이긴하다.
int dp(int src) {
if (src == N - 1) return 1;
if (dport[src]) return dport[src];
int mmax = 0;
for (int i = src+1; i < N; i++) {
if (port[src] < port[i])
mmax = max(mmax, dp(i));
}
return dport[src] = mmax + 1;
}
// 결국 이 문제는 LIS알고리즘 문제로 풀수있는데
// 오름차순 순열중 가장 긴 순열을 찾는 알고리즘으로
// 전체 입력받은 순열을 하나씩 iter하며, 가장 긴 오름차순 순열의 길이를 업데이트하며 체크한다.
//LIS 알고리즘 (Longest Increasing subsequence)
int LIS() {
vector<int> lis;
lis.push_back(port[0]);
// 입력받은 port 벡털르 하나씩 순회한다.
// 순회하면서 최장순열을 업데이트 시키면서 나아간다!!
for (int i = 1; i < N; ++i) {
//다음 순열이 만약 크다면 lis에 원소를 추가하고 증가시킨다.
if (lis.back() < port[i]) lis.push_back(port[i]);
else {
// back보다 작을때만 실행되므로 end()가 반환될 일은 없다.
// port[i]의 lower_bound 조건이 만족되는 index를 찾는다.
int idx = lower_bound(lis.begin(), lis.end(), port[i]) - lis.begin();
lis[idx] = port[i];
}
}
return lis.size();
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
port.resize(N);
dport = vector<int>(N, 0);
port.push_back(2);
for (int i = 0; i < N; i++)
cin >> port[i];
cout << LIS();
}
저는 수학을 전공한 사람이 아니기 때문에 정성적으로만 분석해보겠습니다..ㅎㅎ
알고리즘에서 보듯이 LIS는 나중에 입력된 값을 멋대로 최장길이 순열을 저장하고 있는 vector에 넣고 있습니다.
lis vector 내부는 항상 sort된 상태가 유지 되겠지만, 실제 sort된 순서와 원소가 나열된 순서는 충분히 다를 수 있기 때문에 문제 조건에 맞는 최장길이 순열을 만들지는 못합니다. 그러나!! 길이는 같다고 보장합니다
그건 이 알고리즘이, 멋대로 lis 내부를 바꿔 놓고서는 어쩔때는 값을 바꾼건 맞지만
"아니야!! 이건 사실 예전에 있던 녀석이 맞아!!" 하고 우겨 버리는 개념입니다. ㅎㅎ..
누구를 우기냐!
lis의 마지막 값을 포함한 연속된 원소들 중, 입력된 순서와 sort 순서가 동일한 녀석들까지를 제외 나머지를 예전 값으로 우기면 됩니다! 예를 들어 lis내부가 1, 2, 3, 4, 5, 6 있고 사실은 들어온 순서가 1,4,2,3,5,6 이라면 (5,6)을 제외한 나머지를 우기면됩니다. 4는 sort순서와 들어온 순서가 다르고, 1,2,3,5,6은 순서는 맞으나 lis에서 연속적이지가 않다.
마지막값인 6을 포함해 들어온순서와, sort순서가 맞고 연속적인 배열은 (5,6)이다.
말만 들으시면 무슨말이지? 싶으실텐데 백준 문제를 예시로 들겠습니다
입력순서는 4 2 6 3 1 5
순서대로 lis를 업데이트 시켜보겠습니다. if문에 걸리면 단순 추가, else문에 걸리면 걸린 숫자로 이진탐색한 idx와 교체하게됩니다. (교체 시에는 빨강, 추가는 파랑)
1. 4
2. 2
3. 2 6 실제 순서와 동일하므로 우길 원소가 없습니다.
4. 2 3 //
5. 1 3 1은 3보다 나중에 나왔습니다. 기존값인 2라고 우깁니다! 그래서 아직 2 3입니다!
6. 1 3 5 // 결국 똑같이 우기면 2,3,5 실제 최장 길이 배열과 같지요
2, 1, 6, 8, 4 를 추가로 더 넣어볼까요?
7. 1 2 5 5를 제외하고 모두 들어온 순서가 sort랑 다르므로 예전값인 2 3 5
8. 1 2 5 //
9. 1 2 5 6 6이 추가 되어 마지막 원소인 6을 포함 (5,6)만 순서가 맞아 2 3 5 6
10. 1 2 5 6 8 8이 추가되어 (5,6,8)을 제외한 나머지를 우겨 2 3 5 6 8
11. 1 2 4 6 8 4로 바뀌었기 때문에(6,8)을 제외한 나머지를 우긴다. 2 3 5 6 8
5, 6을 추가로 더 넣어볼까요?
12. 1 2 4 5 8 5로 바뀌었지만, 순서가 맞는 8밖에 인정해 줄수 없습니다. 2 3 5 6 8
13. 1 2 4 5 6 보이시나요? 이제 6을 포함해서 모든숫자가, 들어온 순서와, sort순서가 같습니다!
물론 1은 (8)단계가 아닌 (5) 단계에 들어온 1입니다.(2보다 빨리들어온 1)
6은 (9)단계가 아닌 (13) 단계의 6이고요, (4보다 늦게 들어온 6)
1 2 4 5 6
길이는 같은데 왜? lis 값을 이렇게 바꿨을까요?
만약 그 뒤에 7이 추가된다면, (12)에서는 길이를 못늘렸지만
여기서는 증가가 가능합니다!!
이제 느낌이 오시나요??
이건 새롭게 들어오는 숫자가
lis의 길이를 변화 시키지 않고 그저, 값을 lower_bound(큰것중 가장작은 수)와 바꾸기 때문입니다.
새롭게 들어온 숫자보다 기존에 있던 숫자는 모두 전에 들어왔기 때문에
새로운 숫자보다 sort상 앞에 있는 숫자들은 어차피 얘가 우기든 말든 상관없이 규칙에 어긋나지 않습니다.
어차피 난 얘보다 앞에 있고, 들어온 순서도 더 빠르기 때문입니다.
그렇기 때문에 lis의 마지막 원소가 업데이트 됬을때는 항상 규칙이 성립합니다!!
(가장 최근에 들어온 원소이며, sort상 가장 뒤에 있으므로!!)
하지만 새롭게 들어온 숫자를 sort상 뒤에 있는 숫자들은 인정 할 수 없습니다.
규칙에 어긋나기 때문이죠, 그래서 새롭게 들어온 숫자를 옛날거라고 생각해버리는 겁니다.
그렇다, 혹시라도~ 우연히 sort순서에 맞춰서 순서대로 새로운 숫자들이 lis의 마지막 원소까지 들어온다면
(물론 한개만 들어와도 상관없습니다.) 새롭게 들어온 원소들을 이제부터 진짜처럼 인정해 줄 수 있습니다.
위의 (11) ~ (13)의 단계처럼!!
왜냐면!! sort상 뒤에 온 원소가 더 늦게 들어왔고, 예전부터 있던 원소들은 전부 sort상 앞에 있으니 상관이 없습니다!!
else문은 이런 루틴으로 "길이만큼은" 최장길이를 유지시키며, lis 내부 원소 숫자를 항상 더 작게 유지시키는 알고리즘입니다. 물론 실제 lis는 값이 변하지만, 우리는 논리적으로 이렇게 가정한다면 "길이"만큼은 보장할 수 있게됩니다!
또한 당연히 내부 원소들이 작을 수록 뒤에 추가 시킬수 있는 원소가 더 많아지 겠죠!!
그렇기 때문에 원소를 계쏙해서 lower_bound로 작게 만들 방안을 찾는 것입니다.!!
ex) 만약 너무 앞에 원소를 업데이트 시켜버리면, 당연히 바뀐 원소가 진짜라고 인정받기는 매우 힘들겠죠,
하지만 sort순서에 맞게 새로운 숫자가 맨앞부터 전부 새롭게 들어온다면
완전히 lis내부가 바뀐 새로운 최장순열이 탄생하는 겁니다!!
만약, N long N알고리즘으로 진짜 최장순열의 정체를 알고 싶다면,
lis에 숫자를 하나 넣을때마다 따로 넣은 숫자와, 숫자가 lis에 들어간 index를 기록하게 되면 됩니다.
ex)
pair<int,int> history;
//lis에 숫자가 추가될때마다.
histroy.push_back( { 추가된 숫자, lis에 들어간 idx 위치 })histroy의 뒤쪽일 수록 최근에 lis에 입력을 시도한 숫자들이 오게됩니다.
history의 맨뒤부터 숫자를 살피면, 실제 최장길이 순열의 값인지 아닌지 판단할 수 있습니다.
예로 현재 최장길이가 10이라면, 가장 마지막에 있는 원소의 idx는 9일 것 입니다.
그러면 history맨 뒤에서부터 순서대로 histroy[ ? ].second = 9 인 ?를 찾습니다.
확실히 histroy의 맨뒤에 있는 원소들은 가장 최근에 입력되었지만, lis에 마지막이 아닌 앞쪽에 들어왔다면,
절대 최장 길이 순열에 속할 수가 없습니다. 그렇기 때문에 무시해도 됩니다.
lis의 9 index에 끼워진 많은 수들 중에서 정답이 될 수 있는 수는 여렇개 일 수 있지만,
가장 최근에 들어온, history의 가장 뒤쪽에 있는 second = 9 인 값은 확실하게 믿을 수 있습니다!!
그렇기 때문에 이 숫자는 실제 최장 순열 LIS의 9 idx의 수로 인정해 줍니다.
이제는 8 idx를 찾으면 됩니다. 계속 history의 역순으로 찾고 있기 때문에 9를 이미 찾았기 때문에 이제 찾는 8은 확실히 9보다 일찍들어왔고 값도 작습니다. (늦게 들어온 숫자가 9 idx로 들어왔다는 것은 8 idx 숫자가 더 작다는 것)!!
이것도 8 idx로 확실히 사용 가능하므로 기록!!
이걸 0 idx까지 반복하면 실제 LIS 순열을 찾을 수 있습니다.!!
밑에는 대충 코드입니다.
vector<int> realLIS;
int num = lis.size()-1;
for (int i = histroy.size()-1 ; i >=0; i--)
{
if(history[i].second == num)
realLIS.push_back(history[i].first),num--;
}
// 실제 LIS는 이렇게 만들어진 realLIS vector의 reverse이다!
'Algorithm' 카테고리의 다른 글
| 백준 12100 삼성기출 2480(Easy) (0) | 2020.04.20 |
|---|---|
| 백준 13460번 삼성기출 구술탈출2 (0) | 2020.04.20 |
| 백준 2631 줄세우기 LIS 개념 다이나믹 프로그래밍 (0) | 2020.04.07 |
| 다이나믹 프로그래밍으로 최적화 하는 DFS, 백준 2253번 점프 (0) | 2020.03.28 |
| 백준 1525번 퍼즐 BFS 최단,최소 문제. DFS는 힘든이유.. (0) | 2020.03.22 |
댓글