글 읽기 - Lower_Bound구현이 잘 못 된 건가요???

yoonfy4280 4년 전 1

결과는 다 같게 나오는데,,, 반복 또는 STL을 쓰면 시간 초과가 안 나오고 제가 직접 구현 한 재귀는 시간 초과가 나옵니다 ㅠㅠ.

LIS 알고리즘이 뭔지도 몰라서 LIS 공부하고 직접 재귀로 Lower_Bound구현했는데,, 시간 초과 나왔습니다. 결국 STL을 사용하니 통과, 반복문으로 구현 하면 통과, 이것 때문에 엄청 시간을 소비 했는데,

혹시 고수님들 뭐가 잘 못 된건지 알려주실 수 있으신가요?? 제가 구현한 재귀 Lower_Bound가 틀렸다면 알려주세요 ㅠㅠ.

그리고 LIS 알고리즘에서 LIS 벡터에 들어있는 값이 LIS를 이루는 요소와 무관 한데, 왜 최장의 길이를 보장 해주는지 잘 이해가 안됩니다.

예를들어

4 2 6 3 1 5 라고 할 때,

LIS벡터에 들어가는 순서는

(4) -> (2) -> (2,6) -> (2,3) -> (1,3) -> (1,3,5)

인데, (2,3,5) 가 아닌데, 왜 최장길이를 보장하는지 모르겠습니다.

고수님들 부탁드리겠습니다(_ _).

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

using namespace std;

int Find_Low(vector<int> v, int start, int end ,int item){
    //재귀방식
  int mid = (start + end) / 2;
   
      if(start < end ){
  
      if(v[mid] >= item){
          return Find_Low(v, start, mid, item);
      }
      else if (v[mid] < item){
          return Find_Low(v, mid+1, end, item);
      }
      
      }
      
      return start;

    /* 반복문
 
    while(end-start > 0)      {
        mid = (start+end)/2;
        if(v[mid] < item){ start=mid+1;}
        else end = mid;
        
    }
    return end;
    */
    
}

int main(int argc, const char * argv[]) {
    
    vector<int> v;
    vector<int> LIS;
    int N,item;
    cin>> N;
        
    for(int i = 0; i<N; i++){
        cin >> item;
        v.push_back(item);
    }
    
    LIS.push_back(v[0]);
    
    for(int i=1; i<N; i++){
        
        if(v[i] > LIS.back()){
            LIS.push_back(v[i]);
        }
        else{
            //직접 구현 한 걸로 하면 시간 초과
            int location = Find_Low(LIS, 0, LIS.size()-1, v[i]);
            
            //int location =  lower_bound(LIS.begin(), LIS.end(), v[i]) - LIS.begin();
         
            LIS[location] = v[i];
        }
        
    }
    
    cout << LIS.size();

   
    return 0;
}

kyun2024 4년 전 1

코드에서 함수에 인자는 vector<int>를 받습니다. vector<int>를 통해 선언하면 배열을 복사생성함으로 불필요한 연산을 아주 많이 하게 되는 것이죠. 참조로 고쳐주시면 되고요

그리고 LIS의 최장길이가 확보되는건 그 데이터를 넣을 때의 길이 값이 유지되기 때문입니다.

4 2 6 3 1 5 : (4) -> (2) -> (2,6) -> (2,3) -> (1,3) -> (1,3,5)

에서, 각각 수를 넣을 때 그 자리가 현재까지의 최장길이라는 것을 의미합니다. 2,3,5로 최장길이가 3이 되는 것이지만, 사실은 3으로 끝나는 length=2인 수열에 5를 이어붙이는 연산이라 생각하시면 편하실듯.

댓글을 작성하려면 로그인해야 합니다.