글 읽기 - 어쨰서 양방향에서 탐색해야 TLE가 안뜨는거죠?

smilu2245 3년 전 0

주어진 구간 안에서의 Unique한 원소를 찾을 때, 그냥 왼쪽에서부터(인덱스가 낮은 것부터) 하나씩 검사하는 방법을 사용했더니 TLE가 났습니다.

인터넷에 올라온 풀이를 보니까 양방향에서 병렬적으로 하나씩 찾아야 된다는 언급이 있길래 해봤더니 바로 통과되네요.

푼 거 까지는 좋은데, 그냥 왼쪽부터 찾는거랑 왼쪽오른쪽 동시에 찾는거랑 왜 그렇게 차이가 나는지 잘 모르겠습니다.

// [s, e] 에서 i 번째 원소가 unique한지 O(1) 에 판별
bool unique_range(int i, int s, int e);

int find_unique_1(int s, int e) { // 통과
  int sz = (e-s)>>1;
  for (int i = 0; i <= sz; i++) {
    if (unique_range(s+i,s,e)) return s+i;
    if (unique_range(e-i,s,e)) return e-i;
  }
  return e+1;
}

int find_unique_2(int s, int e) { // 시간초과
  for (int i = 0; i <= e-s; i++) {
    if (unique_range(s+i,s,e)) return s+i;
  }
  return e+1;
}

evenharder 3년 전 4

T(n) = O(n) + T(n-1), T(1) = O(1)이라고 할 때 T(n) = O(n^2)이지만, (각 구간에서 맨 마지막이 정답이 될 때가 최악의 경우입니다)

T(n) = O(n) + T(min(x, n-x)), T(1) = O(1)라 하면 min(x, n-x) <= n/2이기 때문에 T(n) = O(n lg n)이 되기 때문입니다.

바로 재귀탐색이 가능하면 작은 구간에 들어갈 것이며, 최악의 경우에도 이진 트리처럼 조사하게 됩니다.

smilu2245 3년 전 0

아! 단순히 구간 분할만 하면 된다는 생각이 자리잡아서 중요한걸 간과하고 있었네요. 친절한 답변 감사드립니다.

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

문제

문제

출처

ICPC

어쨰서 양방향에서 탐색해야 TLE가 안뜨는거죠?

smilu2245 3년 전 0

evenharder 3년 전 4

smilu2245 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말