글 읽기 - 이분탐색 시간초과 미치겠습니다

darkdulgi 2년 전 0

질문글에 올라온 반례들 다 넣어봤는데 맞게 나오고

정직하게 이분탐색 했는데 자꾸만 시간초과가 나는 거 봐선 어딘가에 무한루프가 생기는 반례가 있는거 같은데 돌아버리겠습니다

혹시나 해서 cin을 scanf로 바꿔봤는데 똑같고요

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	int m;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr.data(), arr.data() + n);
	cin >> m;
	vector<int> brr(m);
	for (int i = 0; i < m; i++)
		cin >> brr[i];

	for (int i = 0; i < m; i++) {
		int index = n / 2;
		int tnum = 2;
		while (1) {
			if(arr[index]==brr[i]){
				brr[i] = 1;
				break;
			}
			else if (arr[index] < brr[i]) {
				if (index == n - 1) {
					brr[i] = 0;
					break;
				}
				else if (arr[index + 1] > brr[i]) {
					brr[i] = 0;
					break;
				}
				index += n / (int)pow(2, tnum);
				if (n / (int)pow(2, tnum) == 0)
					index++;
			}
			else if (arr[index] > brr[i]) {
				if (index == 0) {
					brr[i] = 0;
					break;
				}
				index -= n / (int)pow(2, tnum);
				if (n / (int)pow(2, tnum) == 0)
					index--;
			}
			tnum++;
		}
	}
	
	for (int i = 0; i < m; i++)
		cout << brr[i] << endl;
}

sonjaewon 2년 전 1

이분탐색에서 pow 를 사용하는게 잘못된것 같습니다.

참고로 초기에 tnum 을 log(N) 정도로 잡고 tnum--; 가 되어야 할것 같습니다.

darkdulgi 2년 전 0

아예 pow랑 tnum 버리고 양끝 쪽 인덱스를 나누게 고쳤습니다. 예제들 다 맞게 출력되고요

이 방법이 더 빠를 것 같은데 시간 초과 나는건 똑같네요..

도대체 채점할땐 얼마나 큰 수를 집어넣는건지..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	int m;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr.data(), arr.data() + n);
	cin >> m;
	vector<int> brr(m);
	for (int i = 0; i < m; i++)
		cin >> brr[i];

	for (int i = 0; i < m; i++) {
		int first = 0;
		int last = n - 1;
		int index = last / 2;
		int x = brr[i];
		brr[i] = 0;
		do {
			if (arr[index] == x || arr[first] == x || arr[last] == x) {
				brr[i] = 1;
				break;
			}
			else if (arr[index] < x) {
				first = index;
				index = (index + last) / 2;
			}
			else if (arr[index] > x) {
				last = index;
				index = (index + first) / 2;
			}
		} while ((first != index) && (last != index));

	}

	for (int i = 0; i < m; i++)
		cout << brr[i] << endl;
}

darkdulgi 2년 전 0

알고리즘이 문제인 줄 알고 계속 들여다봤는데 출력을 printf로 바꾸니 맞았네요..

허탈하네요ㅋㅋ

sonjaewon 2년 전 0

cin, cout, endl 이 느려서 그렇습니다.

cin, cout 를 사용하지 않던지, 아니면 최적화를 해줘야 합니다.

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

문제

문제

출처

ICPC

이분탐색 시간초과 미치겠습니다

darkdulgi 2년 전 0

sonjaewon 2년 전 1

darkdulgi 2년 전 0

darkdulgi 2년 전 0

sonjaewon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말