글 읽기 - c++ 이분탐색 시간복잡도 차이

rladbswo12 2년 전 0

이 문제 풀 때,

(주석참고)

1번 방법으로 하면 시간초과 나는데

2번 방법으로 하면 풀립니다!!

왜 시간차이가 나는걸까요!?

공간복잡도 측면에서는 1번 방법이 확실히 나을 것 같고

시간복잡도 측면에서도 2번 방법보다 1번이 더 나을 수 있겠다는 생각이 드는데요!.

알려주시면 감사하겠습니다.

/*
    # 1번 방법
    
    cin >> M;
    int temp;
    for(int i=0; i<M; i++){
        cin >> temp;
        bs(0, N, temp);
    }

    @@@@@@@@@@@@@@@@@@@@@

    # 2번 방법
    
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> arr2[i];
    }

    for(int i=0; i<M; i++){
        bs(0, N, arr2[i]);
    }
*/

/*

숫자 카드 N 개 :
1 <= N <= 500,000
-10,000,000 <= 숫자 <= 10,000,000

정수 M 개 :
1 <= M <= 500,000

@@@@ 풀이방법 @@@@

바이너리 서치

T(NlogN) + T(MlogN) = O(NlogN)

@@@@@@@@@@@@@@@@

*/

#include <iostream>
#include <algorithm>

using namespace std;

int arr1[500001] = {0, };

void bs(int n, int tar) {
    int l = 0;
    int r = n;
    
    while(true) {
        if(l == r) {
            cout << "0 ";
            return;
        }
        
        int mid = (l + r) / 2;
        
        if(arr1[mid] == tar) {
            cout << "1 ";
            return;
        } else {
            if(arr1[mid] < tar) l = mid + 1;
            else r = mid;
        }
    }
}

int main() {
    int N, M;
    
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> arr1[i];
    }
    sort(arr1, arr1+N);
    
    cin >> M;
    int temp;
    // 이 for 문이 에러나는 위치입니다.
    // 위에 주석 봐주시면 감사하겠습니다.
    for(int i=0; i<M; i++){
        cin >> temp;
        bs(N, temp);
    }
        
    return 0;
}

slah007 2년 전 0

전체 코드를 올려주세요.

rladbswo12 2년 전 0

전체 코드 포함해서 다시 올렸습니다!

slah007 2년 전 0

i/o를 열 때마다 시간이 걸리므로 input을 한 번에 받는 것이 약간 더 빠르기야 하겠지만 시간 초과 여부를 결정할 정도는 전혀 아닙니다.

전체 코드를 봐야 하는 이유가 이런 오류가 대부분 fastio 등의 짧지만 중요한 코드를 한쪽에서는 쓰고 다른 쪽에서는 생략하는 경우이기 때문입니다. 저 부분을 빼고 정말 한 글자도 안 틀리고 똑같다면 시간 초과가 날 수가 없다고 생각합니다.

slah007 2년 전 1

제가 조금 잘못 알고 있었던 것이 cin, cout의 경우 input/output stream을 왔다 갔다 하는게 생각보다 훨씬 더 느리네요. 전자는 입력 / 출력이 완전히 분리되어 있고 후자는 입력/출력 * M번을 하므로 훨씬 느립니다.

이것은 cin이 기본적으로 cout과 tie가 되어있기 때문이고 cin.tie(nullptr)을 쓰면 똑같이 통과될 것 같습니다. 자세한 것은 c++의 fast I/O를 검색해서 찾아보세요.

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

문제

문제

출처

ICPC

c++ 이분탐색 시간복잡도 차이

rladbswo12 2년 전 0

slah007 2년 전 0

rladbswo12 2년 전 0

slah007 2년 전 0

slah007 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말