FamilyTree 문제 시간초과 입니다. 검토 부탁 드립니다.

  • kwangswei
    kwangswei

    안녕하세요.
    Family Tree 문제 풀고 있습니다.
    입력이 매우 크므로 가능한 빠른 입력을 쓰라고 문제에 나와있는데 어떤 system call 을 쓰는 것이 좋은지요?
    제출해보니 시간 초과가 되고 있습니다.

    덧붙여 알고리즘이 느려서 그런 것은 아닌지 검토 부탁 드립니다.
    배열로 자신의 부모와 트리에서의 레벨을 저장한 후에,
    입력된 두 노드의 레벨이 같도록 레벨이 큰 놈을 조절한 후,
    같이 부모를 찾아서 트리의 상위 레벨로 올라가는 형태입니다.

    알고리즘 설명이 복잡한 것 같아 추가 합니다.

    1. 노드1(N1)의 레벨(L1), 노드2(N2)의 레벨(L2) 를 비교한다.
    2. L1과 L2를 대소 비교하여 L1' == L2' 가 되도록 부모 노드로 이동한다. 이 때 촌수를 누적시키며 이동.
    3. L1' == L2' 가 같아지면 동일한 부모를 가질 때까지 두 노드 모두 부모를 찾아 올라간다. 두 노드가 한 꺼번에 올라가므로 촌수는 2씩 증가한다.

    감사합니다.

    #include <stdio.h>

typedef struct _FamilyTree
{
    int parent;
    int level;
} FamilyTree;

enum {NMAX=100000, QMAX=10000};

void init   (FamilyTree* tree, int N);
void input  (FamilyTree* tree, int Q);
int  calc   (FamilyTree* tree, int n1, int n2);

int main()
{
    int i;
    int C;
    int N, Q;
    int n1, n2;
    FamilyTree tree[NMAX];

    scanf("%d", &C);
    while ( C-- )
    {
        scanf("%d %d", &N, &Q);
        init(tree, N);
        input(tree, N);

        for (i = 0; i < Q; i++ )
        {
            scanf("%d %d", &n1, &n2);
            printf("%d\n", calc(tree, n1, n2));
        }
    }

    return 0;
}

void init(FamilyTree* tree, int N)
{
    int i;
    for ( i = 0; i < N; i++ )
        tree[i].parent = tree[i].level = 0;
}

void input(FamilyTree* tree, int N)
{
    int i;
    int parent;
    for ( i = 1; i < N; i++ )
    {
        scanf("%d", &parent);
        tree[i].parent = parent;
        tree[i].level = tree[parent].level + 1;
    }
}

int calc(FamilyTree* tree, int n1, int n2)
{
    int i;
    int degree = 0;

    if ( n1 == n2 )
        return 0;

    if ( tree[n1].level < tree[n2].level )
        return calc(tree, n2, n1);

    if ( tree[n2].level == 0 )
        return tree[n1].level;

    degree = tree[n1].level - tree[n2].level;
    for ( i = 0; i < degree; i++ )
        n1 = tree[n1].parent;

    while ( n1 != n2 )
    {
        n1 = tree[n1].parent;
        n2 = tree[n2].parent;
        degree += 2;
    }

    return degree;
}

    12년 전
12개의 댓글이 있습니다.
  • JongMan
    JongMan

    이렇게 푸시면 결국 시간 복잡도는 O(QN)이 됩니다. Q=10000, N=100000 이므로 이대로라면 시간안에 풀기는 힘들죠. 이 문제는 특정 자료 구조를 잘 이용해서 한 질문을 O(lgN)에 대답해서 풀어야 합니다.


    12년 전 link
  • JongMan
    JongMan

    실제로는 테스트 데이터가 약해서 O(QN)으로 제출하신 분들도 맞으신 분들이 좀 있습니다 -_-;; 나중에 리저지할꺼에요..


    12년 전 link
  • kwangswei
    kwangswei

    시간 복잡도가 O(QN) 이 된다는 것이 잘 이해가 안되는데 혹시 좀 더 자세히 설명 가능한지요?

    제가 생각하기에는 많이 찾아봐야 부모를 타고 올라가 루트에 다다르면 끝날 것이고, 두 Q가 동시에 올라가므로 시간복잡도 O(QN) 보다는 낫지 않나 합니다.


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    100000 10000
    0 1 2 3 4 5 6 7 8 ...
    0 99999
    0 99999
    0 99999
    .
    .
    .

    이런 경우를 말하는 거겠죠...?
    아마 시간 내에 돌긴 힘들 것 같네요..


    12년 전 link
  • kwangswei
    kwangswei

    @Taeyoon_L 데이터가 그렇게 구성된 경우에는 물론 수행 시간은 QN이 되겠지만 시간 복잡도는 입력 데이터가 랜덤 분포를 따른다고 보는 것이 아닌가요? 그건 그렇고 해당 케이스를 해결하기 위해 고민을 해봐야겠군요~!. 조언 감사합니다~!


    12년 전 link
  • kwangswei
    kwangswei

    간단하게 Taeyoon_L 님이 지적해주신 부분 계산해서 반환하게 만들고 나니 "오답" 이 뜨네요 ㅠ.ㅠ 뭐가 문제지... -_-;;;


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    프로그래밍 대회에서 입력 데이터는 매우 주관적입니다. 랜덤 분포를 따른다는 보장은 어디에도 없어요.


    12년 전 link
  • kwangswei
    kwangswei

    @Taeyoon_L 네, 프로그래밍 대회에서의 입력데이터가 아니라 O 표기법에서의 입력데이터를 말한 것인데, 본 문제 논지와는 별 상관 없겠네요 ^^;;;


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    시간 복잡도도 O(QN)이 맞습니다. 랜덤 분포와 O표기법은 관련이 없어요. 랜덤 분포에 대해선 expected O라고 표기하는 걸 보긴 한 것 같네요...


    12년 전 link
  • kwangswei
    kwangswei

    흠.. 인터넷을 검색하다가 보니 각각의 케이스마다 모두 Big O 표기법을 쓰는군요. Wikipedia(http://en.wikipedia.org/wiki/Computational_complexity_theory)를 봐도 그렇구요.

    그렇지만 프로그래밍 대회 관점에서는 말씀하신 worst-case complexity 를 기준으로 하는게 맞는 것 같습니다. 감사합니다~!!


    12년 전 link
  • JongMan
    JongMan

    넵, expected time/worst time/best time과 Big O 표기법은 아무런 관련이 없습니당. expected time/worst time/best time은 입력의 크기에 대한 함수고, Big O 표기법은 주어진 함수를 간단하게 표기하기 위한 방법일 뿐이지요.
    프로그래밍 대회에서는 대개 worst time complexity 를 테스트하기 때문에 이에 대비해야 합니다. ^^


    12년 전 link
  • kwangswei
    kwangswei

    Mastojun 군이 Worst Case 에 대한 경우의 처리와 Input 데이터가 달라질 경우 Level 이 제대로 계산될 수 없는 문제를 지적해주었습니다.

    트리로 표현한 후에 한 노드를 기준으로 트리를 돌려서 DFS 를 하는 방법을 써봐야겠네요. ㅠ.ㅠ


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.