ksjb2897   1년 전

계속 8퍼센트에서 시간초과가 뜹니다...

질문게시판에 있는 시간초과 내용을 전부 살펴봐도 제 케이스에 해당되지 않는 문제인 것 같습니다. (높이가 0인 직사각형, 너비가 2인 직사각형, long long, 배열 초기화 등등...)

제가 짠 알고리즘부터 설명드리면,

dq라는 함수는 left 인덱스부터 right 인덱스까지의 문제에서 요구하는 최댓값을 구하는 함수입니다.

dq라는 함수는 마지막에 left부터 mid와 mid부터 right까지의 각각의 dq값을 비교합니다.

하지만 이렇게 하면, 직사각형이 mid와 mid+1을 동시에 지날 때의 값을 구할 수 없어서, 이 두 구간을 동시에 지날 때의 최댓값을 구하는 함수 g를 만들었습니다.

그렇게 해서 dq는 최종적으로 절반 구간의 dq의 값들과 g의 값을 비교하여 최댓값을 산출합니다.

여기서 g의 시간복잡도가 관건이라고 생각했고, g의 시간복잡도를 n이하로 만들고 싶었습니다.

그렇게 해야 합병정렬을 할 때처럼 시간복잡도가 나오기 때문입니다.

이제 

그렇게 해서 g를 구현한게,

1) 모든 구간을 오르막 한번, 내리막 한번만 되게 구간을 만듭니다. 이 때, mid와 mid + 1에서 최댓값을 가지게 만듭니다. (코드 45~56)

예를 들어, 3 1 2 7 5 6 2 4가 주어지면,

이를 1 1 2 7 5 5 2 2로 만듭니다. (이때, 원래 배열은 보존하기위해서 cpy_a를 만들어서 안전하게 진행했습니다..!)

::::: 시간 복잡도 : N

2) 그러고 나서 이를 내림차순 정렬 합니다. 하지만 이 때, merge sort 처럼 이를 2개의 배열로 나누고, 합치면서 정렬을 합니다.(코드 57, 코드 9~39)

예를 들어, 1 1 2 7 5 5 2 2를 1 1 2 7과 5 5 2 2로 쪼갭니다. 이 때, 왼쪽배열은 오름차순이고 오른쪽 배열은 내림차순이므로 차례대로 원소를 비교하여

7 5 5 2 2 2 1 1 로 만듭니다.

:::::: 시간 복잡도 : N

3) 이러고 각 원소마다, 그 원소의 높이 이상을 가지는 개수만큼 곱해서 넓이를 구한 후, 최댓값을 구했습니다. 이 때, index를 이용하여 한번에 계산했습니다.(코드 58~67)

예를 들어, 

높이를 7로 가지는 직사각형 : 7 X 1 (7이상인게 하나뿐)

높이를 5로 가지는 직사각형 : 5 X 3 (5이상인게 3개임)

높이를 2로 가지는 직사각형 : 2 X 6 (2이상인게 6개)

높이를 1로 가지는 직사각형 : 1 X 7 (1이상인게 7개)

이렇게 구한 후(인덱스가 있기 때문에 각 높이마다 시간복잡도 1로 계산 가능합니다 ㅠ)

최댓값을 구해줍니다.

:::::: 시간 복잡도 : N

이렇게 최종 결과물을 분할된 dq와 진행하여 구하는 과정이였습니다.

이렇게 계산하면,

계산횟수를 f(N)이라고 할 때,

f(N) = f(N/2) + f(N/2) + N + N + N = 2*f(N/2) + 3N

이 되어, 

O(NlogN)의 시간복잡도를 가지는데, 왜 시간초과가 나오는지 모르겠습니다.

간절합니다 ㅠㅠ 여러분 도와주세요...

bnb2011   1년 전

g 함수를 호출하는 횟수가 O(NlogN)번인데, 매번 g 함수를 호출할 때마다 10만 칸의 배열 할당을 하고 있으니 시간 초과가 날 수밖에 없습니다.

cpy_a 배열을 전역으로 옮긴 뒤, 필요한 칸만 초기화해서 사용해보세요.

ksjb2897   1년 전

cpy_a배열을 전역으로 옮겨도 시간초과가 나요 ㅠㅠ

cpy_a를 선언할 때는 배열의 크기와 상관없이 O(1)로 알고 있는데, 그럼 선언자체로 드는 시간이 O(NlogN)이라 상관 없지 않나요?

그리고 또, cpy_a에 a의 원소들을 카피하는 과정은, left에서 right만 할당하기에, 

전체적으로 NlogN의 시간만 걸리는거 아닌가요?

(에를들어 8개의 원소로 진행을 하면, 

8개

4개 4개

2개 2개 2개 2개

이므로 8Xlog8)

ksjb2897   1년 전

마찬가지로 tmp도 전역변수로 바꿨는데도 해결이 안됩니다 ㅠ

ksjb2897   1년 전

해결했습니다!!

문제가

#define max(a,b,c) 이쪽이였습니다..!

아직 잘 안배워서 모르겠는데 #define으로 정의하면 시간복잡도를 많이 잡아먹는 것 같습니다 ㅠㅠ (아마 a,b,c가 long long int라 그런가..?)

그래서 max함수를 define으로 말고 따로 함수로 정의해줬더니 통과했습니다 ㅠㅠ

zenith82114   1년 전

범인은 max 매크로입니다. max(a, b, c)에서 a > b이고 a > c이면 a는 최대 3회 평가됩니다. a 자리에 오는 것이 그냥 변수면 문제가 없겠지만, 연산식이나 함수 호출인 경우 고스란히 3회의 계산이나 호출이 발생합니다. max(dq(left, mid), dq(mid + 1, right), g(left, right))는

((dq(left, mid) > dq(mid + 1, right))
    ? ((dq(left, mid) > g(left, right)) ? dq(left, mid) : g(left, right))
    : ((dq(mid + 1, right) > g(left, right)) ? dq(mid + 1, right) : g(left, right)))

이라고 쓰는 것과 동일하기 때문입니다.

따라서 dq 함수에서 return문을 다음으로 교체하면 정답을 받을 수 있습니다.

long long int left_dq = dq(left, mid);
long long int right_dq = dq(mid + 1, right);
long long int mid_g = g(left, right);
return max(left_dq, right_dq, mid_g);

ksjb2897   1년 전

우와.. 구체적인 설명 감사합니다..!

매크로 쓸 때는 항상 이 점을 고려해야 겠군요 감사합니다!

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