caveman 알고리즘 질문드립니다. sven CAVEMAN 제 알고리즘이 TLE가 뜨는데요, 어떻게 더 개선하면 좋을까요? 각 횃불에 대해, 횃불이 밝히는 범위 중 작은 쪽의 경계 좌표(coverage)를 기준으로 소트를 합니다. current 변수에, 아직까지 밝혀지지 않은 가장 왼쪽의 횃불의 좌표를 저장합니다. 그리고 매 순간 이진 탐색을 통해 그 좌표를 커버하는 횃불들 중 가장 넓은 범위를 커버하는 (위치 + 크기의 최댓값)횃불을 찾아 범위를 갱신하고 계속합니다. 세세하게는, 이진 탐색은 같은 값을 갖는 경우 횃불 중 가장 우측 (큰 쪽 방향의) 횃불을 넘겨줍니다. (우극한 느낌) 그리고 그 결과부터, 하나씩 왼쪽 (작은 쪽 방향)으로 보면서 원하는 횃불을 찾습니다. 이 과정에서, 매 반복마다 결정된 횃불의 값을 head에 저장하여, 그 이하의 부분은 이후의 이진 탐색에서 탐색하지 않도록 합니다. 어떤 부분을 더 줄일 수 있을까요? 무한 루프로 인하여 TLE가 발생하는지 의심되어, 여러 assert문을 넣었으나, 무한 루프로 인한 문제는 아닌 것 같습니다. #include <iostream> #include <vector> #include <algorithm> #include <cassert> using namespace std; void solve(); int flag; class D { public: int pos, val; D(int a, int b) { pos = a; val = b; } int coverage() { return pos - val + 1; } bool friend operator < (D A, D B) { return A.coverage() < B.coverage(); } static int binary_search(vector <D> A, int B, int head, int tail) { if(tail - head == 0) return head; else if(tail - head == 1 && A[tail].coverage() <= B) return tail; else if(tail - head == 1 && A[tail].coverage() > B) return head; int mid = (head + tail) / 2; if(A[mid].coverage() > B) return binary_search(A, B, head, mid); else return binary_search(A, B, mid, tail); return -1; } }; int main(int argc, const char * argv[]) { int T; cin >> T; while(T--) solve(); return 0; } void solve() { int N; vector <D> A; cin >> N; for(int i=0; i<N; i++) { int temp; cin >> temp; A.push_back(D(i,temp)); } sort(A.begin(), A.end()); int current = 0; int count = 0; int head = 0; while(current < N-1 && ++count) // N { int index = D::binary_search(A, current, head, N-1); // log N int index_save = index; int target = -1; index++; while(index >= head && index--) // <= N { assert(A[index].coverage() <= current); if(A[index].pos > A[target].pos || target == -1) target = index; } assert(target >= 0); assert(head < index_save + 1); head = index_save + 1; current = A[target].pos + A[target].val; assert(count <= N); } cout << count << endl; } 12년 전
5개의 댓글이 있습니다. JongMan 일단 입력이 크니까 scanf()를 써보시거나 cin.sync_with_stdio(false)를 해보시면 어떨까요? 12년 전 link sven 수정하였으나 여전히 TLE가 뜨는군요. ㅜㅜ 12년 전 link JongMan 자세하게는 안봤습니다만 겹쳐져 있는 while 문 때문에 시간이 오래 걸리는 것 같은데요. 바이너리 서치를 해서 빠르게 index를 찾아봐야 다시 왼쪽으로 쭉 가면서 하나하나 가장 오른쪽에 있는 걸 찾고 있으니 소용이 없는 듯요. 좀더 단순하지만, 소트를 하고 난 다음에 선형시간으로 푸는 방법이 있습니당. 고민해보세용 =3=3 12년 전 link sven 해결했습니다. 감사합니다! 12년 전 link JongMan 축하요~ ^^ 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sven
CAVEMAN
제 알고리즘이 TLE가 뜨는데요, 어떻게 더 개선하면 좋을까요?
각 횃불에 대해, 횃불이 밝히는 범위 중 작은 쪽의 경계 좌표(coverage)를 기준으로 소트를 합니다.
current 변수에, 아직까지 밝혀지지 않은 가장 왼쪽의 횃불의 좌표를 저장합니다. 그리고 매 순간 이진 탐색을 통해 그 좌표를 커버하는 횃불들 중 가장 넓은 범위를 커버하는 (위치 + 크기의 최댓값)횃불을 찾아 범위를 갱신하고 계속합니다.
세세하게는, 이진 탐색은 같은 값을 갖는 경우 횃불 중 가장 우측 (큰 쪽 방향의) 횃불을 넘겨줍니다. (우극한 느낌) 그리고 그 결과부터, 하나씩 왼쪽 (작은 쪽 방향)으로 보면서 원하는 횃불을 찾습니다.
이 과정에서, 매 반복마다 결정된 횃불의 값을 head에 저장하여, 그 이하의 부분은 이후의 이진 탐색에서 탐색하지 않도록 합니다.
어떤 부분을 더 줄일 수 있을까요? 무한 루프로 인하여 TLE가 발생하는지 의심되어, 여러 assert문을 넣었으나, 무한 루프로 인한 문제는 아닌 것 같습니다.
12년 전