글 읽기 - 시간초과 문제

rnjstpgns91 3년 전 0

처음에는 구조체안에 vector를 이용해서 char문자를 붙이는 방식으로 구현하였으나 시간초과가 발생하였습니다.

질문게시판을 참고하니 이런방식보단 이전의 상태를 기록하는 방식이 시간적으로 많은 이득이라는 글을 보고 이전상태를 기록하는 방식으로 바꾸었습니다.

하지만 똑같이 3%대에서 시간초과가 걸리는데 어떤 점이 문제를 발생시키는지 알려주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

//구조체 안에 char붙여 나가면 배열을 함께 움직여야되서 시간이 많이 걸림. 이전장소에서의 상태를 기록하는 방식으로

int A, B;

struct point
{
	int pre;
	char state;
};

point visit[10001];

void input()
{
	cin >> A >> B;
}

int calL(int X)
{
	int Arr[4] = { 0 };
	int idx = 1;
	while (X > 0)
	{
		Arr[idx] = X % 10;
		idx++;
		if (idx == 4) idx = 0;
		X /= 10;
	}

	int res = 0;
	for (int i = 0; i < 4; i++)
		res += (Arr[i] * pow(10, i));

	return res;
}

int calR(int X)
{
	int Arr[4] = { 0 };
	int idx = 3;
	while (X > 0)
	{
		Arr[idx] = X % 10;
		idx++;
		if (idx == 4) idx = 0;
		X /= 10;
	}

	int res = 0;
	for (int i = 0; i < 4; i++)
		res += (Arr[i] * pow(10, i));

	return res;
}

void BFS()
{
	for (int i = 0; i < 10001; i++)
	{
		visit[i].pre = -1; //값이 0인경우도 있을 수 있으므로 -1로
		visit[i].state = 0;
	}	

	queue<int> q;
	q.push(A);
	visit[A].pre = -1;
	visit[A].state = -1;

	while (!q.empty())
	{
		int X = q.front();
		q.pop();

		if (X == B)
			return;

		//D
		int nx = 2 * X;
		if (nx >= 10000) nx %= 10000;
		if (visit[nx].pre == -1) //방문 기록이 없을 때
		{
			visit[nx].pre = X; //방문표시
			visit[nx].state = 'D'; //어떤 연산으로 왔는지 표시
			q.push(nx);
		}

		//S
		if (X == 0) nx = 9999;
		else nx = X - 1;
		if (visit[nx].pre == -1)
		{
			visit[nx].pre = X;
			visit[nx].state = 'S';
			q.push(nx);
		}

		//L
		nx = calL(X);
		if (visit[nx].pre == -1)
		{
			visit[nx].pre = X;
			visit[nx].state = 'L';
			q.push(nx);
		}

		//R
		nx = calR(X);
		if (visit[nx].pre == -1)
		{
			visit[nx].pre = X;
			visit[nx].state = 'R';
			q.push(nx);
		}
	}
}

void solve()
{
	BFS();

	int idx = B;
	vector<char> v;
	while (1)
	{
		if (idx == A) break;
		v.push_back(visit[idx].state);
		idx = visit[idx].pre;
	}

    //역추적했으므로 역으로 출력해야 올바른 순서
	for (int i = v.size() - 1; i > -1; i--) 
		cout << v[i];
	cout << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while (T--)
	{
		input();
		solve();
	}

	return 0;
}

djm03178 3년 전 3

pow가 문제입니다. pow는 실수형으로 연산하기 때문에 정수형에 비해 훨씬 느립니다.

10의 거듭제곱들을 미리 계산해두면 여유있게 통과됩니다.

rnjstpgns91 3년 전 0

답변 감사합니다.

쓰기 편해서 자주 쓰는 함수인데 이 함수가 문제가 될 때도 있군요...

혹시 추가적인 질문이 가능하다면,

pow의 시간이 얼마나 되길래 궁금해서 구글링해보니 1년전에 다른 글에 답변해주신 것(마침 그분도 라이브러리의 pow함수와 사용자 정의 pow함수의 속도비교에 대한 의문)+다른 글들 보니 일정범위안에서는 상수시간의 시간복잡도라는 것을 보았습니다.

위에서 pow(10, i)의 경우 i가 최대 3까지인 큰 수가 아니라서 일반적인 부분에 해당하는 상수시간 시간복잡도를 갖고 있다고 생각하는데 실수형의 연산이 정수형에 비해 훨씬 느리다고 해도 답에 영향을 준다는게 잘 이해가 되지 않습니다.

어떤 부분을 더 찾아보면 좋을까요?

https://hashcode.co.kr/questions/2048/c-%EC%8B%A4%EC%88%98-%EC%97%B0%EC%82%B0-%EC%A0%95%EC%88%98%EC%97%B0%EC%82%B0-%EC%86%8D%EB%8F%84-%EC%B0%A8%EC%9D%B4

위 링크 답변에서 약 43억번의 연산을 했을 때 3초정도 차이가 난다는 글을 참고하였습니다.

djm03178 3년 전 1

상수 시간의 복잡도라는 것 자체가 실제로 그 연산이 얼마나 느린가를 보여주는 것은 아닙니다. 예를 들어 printf("Hello World!");도 상수 시간에 동작하지만 이것과 i++;의 속도 차이는 비교할 수 없을 정도로 큽니다.

또한 pow 함수가 단순히 수가 작다고 해서 더 빠르지는 않고, 특수 케이스 일부에 대해서만 먼저 걸러내기 때문에 특별히 빠르다고 알고 있습니다. 사실 pow가 느린 진짜 이유는 단순히 정수 / 실수의 차이가 문제보다도, pow 자체가 많은 연산의 복합체이기 때문입니다.

https://github.com/lattera/gli...의 __ieee754_pow 함수 부분을 참고하세요.

rnjstpgns91 3년 전 0

감사합니다 ㅎㅎ

다른 문제의 댓글을 통해서도 그렇고 많이 도움을 받고있습니다.

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

문제

문제

출처

ICPC

시간초과 문제

rnjstpgns91 3년 전 0

djm03178 3년 전 3

rnjstpgns91 3년 전 0

djm03178 3년 전 1

rnjstpgns91 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말