6주차: 이분탐색과 LIS

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 IT취업 자료구조 문제풀이 - 인프런 | 강의

 

https://blog.naver.com/jhc9639/222335391575

[알고리즘 강의] 6주차. 이분탐색과 LIS(최대증가부분수열)

 

위 수업을 듣고 정리한 글입니다.

 

이분탐색

원소 존재여부를 확인할때, n이 매우 크고 O(logN)만에 처리해야되는 경우 시도하는 알고리즘

 

• 정렬된 배열에서 배열의 원소값과 대상값을 비교한다.

이분탐색 -  질문에 대한 true , false 구하기

 

 

2271번: 암기왕 -이분탐색으로 원소 찾기

시간 제한              메모리 제한             제출             정답             맞힌 사람             정답 비율

 

2 초

256 MB

20848

6874

4447

30.604%

 

문제

 

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

 

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에  ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

 

출력

 

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 1 복사

1
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

 

 

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

2776번: 암기왕

 

시간복잡도: 백만*백만 .. 원소 탐색에 시간이 너무 많이 걸린다 => 이분탐색 이용

 

sort() : O(N logN)의 시간복잡도

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;
int t,n,m,temp;

int check(int temp, vector<int> &v){
    int l=0; int r=v.size()-1;
    int mid;
    while(l<=r){
        mid = (l+r)/2;
        if(v[mid]>temp) r=mid-1; //찾으려는 숫자가 더 작음
        else if(v[mid]==temp) return 1; //찾음
        else l=mid+1; //찾으려는 숫자가 더 큼
    }
    return 0; //찾지 못하면 0
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> t;
    while(t--){
        vector<int> v;
        cin >> n;
        for(int i=0;i<n;i++){
            cin>> temp; v.push_back(temp);
        }
        sort(v.begin(), v.end()); //이분탐색을 하기위해 정렬
        cin >> m;
        //2. 이분탐색 수행
        for(int i=0;i<m;i++){
            cin>> temp;
            cout << check(temp,v) << "\n";
        }

    }


}

이진탐색은 오름차순 정렬 후 수행한다!

• 테스트케이스마다 반복되는 수행문일경우 변수 초기화에 유의하자.
• sort함수를 배열에서 사용시 초기화된 값(ex)0)이 맨 앞으로 몰릴 수 있으므로 입력받은 범위만큼만 매개변수로 넣자. =>헷갈리면 벡터를 사용하자.

// sort(a, a+MAX); 아님..
sort(a, a+n);

 

 

 

 

"작게 골고루 쪼갤때도 이분탐색을 사용한다"

=> 이 숫자로 나눠질 수 있는가?

=> 큰 숫자부터 작은 숫자까지 계속 나눈다.

 

2792번: 보석 상자

 

보석 상자 

다국어

한국어   

시간 제한            메모리 제한           제출           정답           맞힌 사람           정답 비율

 

1 초

128 MB

6083

2176

1620

37.491%

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, 109]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

 

출력

첫째 줄에 질투심의 최솟값을 출력한다.

예제 입력 1 복사

5 2
7
4

예제 출력 1 복사

3

 

예제 입력 2 복사

7 5
7
1
7
4
4

예제 출력 2 복사

4

 

 

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

2792번: 보석 상자

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,m, a[300004], ret=1e18;

bool check(ll mid){
    ll num=0;
    for(int i=0;i<m;i++){ //m개의 보석에 대해        
        num += a[i]/mid; //mid로 나눠진 묶음
        if(a[i]%mid) num++; //mid보다 작은 마지막 묶음
    }
    return n>=num; //학생>=나눠진 묶음이면 잘 나누어짐, 그렇지않으면 학생보다 묶음이 더 많음
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n >> m;
    ll lo=1, hi=0, mid;
    for(int i=0;i<m;i++){ //m개의 보석
        cin >> a[i];
        hi = max(hi, a[i]); //a[i]중에 가장 큰것을 hi로 잡기
    }
    //2. 이분탐색 수행
    while(lo<=hi){
        mid = (lo+hi)/2;
        if(check(mid)){ //mid로 잘 묶어지면
            ret = min(ret,mid); //더 작은걸로 묶기
            hi=mid-1; //
        } else lo=mid+1;
    }
    cout << ret <<"\n";

    return 0;
}

 

정리한 코드

#include <bits/stdc++.h>
using namespace std;

int n,m, a[300004], lo=1, hi,mid,ret=987654321;

bool check(int mid){
    int num=0;
    for(int i=0;i<m;i++){
        num += a[i]/mid;
        if(a[i]%mid) num++;
    }
    return n>=num;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a[i];
        hi = max(hi,a[i]);
    }
    //2. 이분탐색 수행하기
    while(lo<=hi){
        mid = (lo+hi)/2;
        if(check(mid)){
            ret = min(ret,mid);
            hi=mid-1;
        }
        else lo=mid+1;
    }
    //3. 정답 출력하기
    cout << ret;
}

• lo=1로 하지않고 lo=0으로 하면 hi=0이 가능하므로 mid가 0이 되어 DividedByZero 에러가 발생가능하다.
  • left=1로 시작하자. left 값은 점점 늘어나고, right값은 점점 줄어드므로 right=1을 해서는 또 DividedByZero 에러가 발생한다.
  • 보석마다 배열의 크기가 다르다보니 생기는 것 같다. 오류를 잘 기억하자

 

LIS

가장 긴 증가하는 부분 수열 

성공

 

시간 제한             메모리 제한            제출            정답            맞힌 사람            정답 비율

 

1 초

256 MB

130146

51366

33897

37.439%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

 

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

11053번: 가장 긴 증가하는 부분 수열

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], cnt[1004],ret;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++) cin>>a[i];
    //2. 가장 긴 증가하는 부분 수열 구하기 ->10 20 10 30 20 50 
    for(int i=0;i<n;i++){
        int maxValue=0; //증가하는 부분수열의 끝점을 가리킬 변수
        for(int j=0;j<i;j++){ //i앞에 있는 수열 숫자 탐색
            if(a[j]<a[i] && maxValue<cnt[j]) maxValue=cnt[j]; //오름차순일경우 가장 길이 큰 값을 반환하고
        }
        cnt[i]=maxValue+1; // 현재 원소를 추가하므로 길이+1
        ret=max(ret,cnt[i]); //길이 최대값(수열의 길이) 출력
    }
    //3. ret(오름차순 수열 최종 길이) 출력하기
    cout << ret;
    
}

 

 

가장 긴 증가하는 부분 수열 4 

스페셜 저지

 

시간 제한.         메모리 제한        제출        정답        맞힌 사람        정답 비율

 

1 초

256 MB

30741

12074

9167

39.305%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4
10 20 30 50

 

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

14002번: 가장 긴 증가하는 부분 수열 4

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], prev_list[1004], cnt[1004],ret=1, idx;
vector<int> r;

void go(int idx){
    if(idx==-1) return;
    r.push_back(a[idx]);
    go(prev_list[idx]);
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    //2. prev_list를 -1로, cnt 배열을 1로 초기화
    fill(prev_list, prev_list+1004, -1);
    fill(cnt, cnt+1004, 1);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[i]<a[j] && cnt[i]<cnt[j]+1){ //숫자 같을때도 포함
                cnt[i]=cnt[j]+1; //cnt[i]는 cnt[j]의 최대값 +1
                prev_list[i]=j; //이전값 저장
                if(ret<cnt[i]){
                    ret=cnt[i]; //수열의 최종길이
                    idx=i; //마지막 인덱스 구하기 위해서 사용
                }
            }
        }
    }
    cout << ret<< "\n";
    //3. 뒤에서부터 앞으로 원소값 추적하기
    go(idx);
    //출력하기
    for(int i=r.size()-1;i>=0;i--){
        cout << r[i] << " ";
    }

}

 

다시 정리해본 코드

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], cnt[1004], prev_list[1004],ret=1, idx;
vector<int> v;

//뒤 -> 앞으로 
void go(int idx){
    if(idx==-1) return; //더이상 앞으로 갈 수 없으면 종료
    v.push_back(a[idx]); //원소 벡터에 저장
    go(prev_list[idx]); //이전 노드를 가리키고 재귀호출
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    //초기화
    fill(cnt, cnt+1004, 1); //수열의 길이 저장
    fill(prev_list, prev_list+1004, -1); //prev_list: 이전노드 저장
    //2. 증가하는 부분수열 만들기
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i] && cnt[i]<cnt[j]+1){ //오름차순이고 길이가 업데이트 되지 않았으면
                cnt[i]=cnt[j]+1; //길이 업데이트
                prev_list[i]=j; //이전 노드 저장
                //최대 출력 길이 업데이트
                if(ret<cnt[i]){
                    ret = cnt[i];
                    idx = i; //증가하는 부분수열의 맨 마지막 인덱스로 갱신
                }
            }
        }
    }
    cout << ret << "\n"; //부분수열의 길이 출력
    //3. 부분수열 원소 추적하기(뒤->앞)
    go(idx);
    //4. 역순으로 하여 출력하기
    reverse(v.begin(), v.end());
    for(int a:v){
        cout << a <<" ";
    }
}

• cnt와 ret이 1부터 시작하는 이유는 맨 처음 원소는 항상 LIS에 포함되기 때문이다.

LIS - lower_bound 이용

#include <bits/stdc++.h>

using namespace std;

int n, lis[1001], len, num;

int main(){

ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

//1. 입력하기

cin >> n;

for(int i=0;i<n;i++){

cin >> num;

auto lowerPos = lower_bound(lis, lis+len, num);

cout << "lostPos:" << lowerPos << " ";

cout << "*lostPos :" << *lowerPos << " ";

if(*lowerPos==0) len++; //더 큰값이 없다면 그냥 추가, 아니면 덯어쓰기

*lowerPos=num;

for(int j=0;j<n;j++)

cout << lis[j];

cout << "\n";

}

cout << len;

 

}