글 읽기 - 시간 초과....

sium 7년 전 0

코드는 문제에서 원하는 결과를 출력하는데, 값이 조금만 커져도 시간 초과가 뜨네요.

재귀함수를 이용하여 조합순열을 구한 뒤에 비교하여 맞는지 틀린지 출력하도록 했는데,

시간을 줄이는 방법이 있나요?

아니면 처음에 접근 방법이 틀린건가요??ㅠㅠ

#include<stdio.h>
int End=0;
int comb(int input[], int set[], int set_size, int n, int k, int index, int fix)
{
    int i=0;
    if(End==1)
        return 1;
    if(k==0)
    {
        if(comp(input, set, fix)==1)
        return 1;
    }
    
    else if (index == n)
    {
    return 0;
    }
    else
    {
        if(End==1)
               return 1;
        set[set_size]=index;
        comb(input, set, set_size+1, n, k-1, index+1, fix);
        comb(input, set, set_size, n, k, index+1, fix);
       
    }
}

int comp(int input[], int set[], int fix)
{
    int i=0;
    
    for(i=0; i<fix-1; i++)
    {
        if(input[set[i+1]]<=input[set[i]])
            return 0;
        if(i==fix-2)
        {
            End=1;
            printf("1\n");
            return 1;
        }
    }
    return 1;
}

int main()
{
    int i,j;
    int N[100]={0,};
    int K[100]={0,};
    int input[100][10000]={0,};
    int T=0;
    int set[100],n,k;
    
    scanf("%d", &T);
    for(i=0; i<T; i++)
    {
        scanf("%d %d", &N[i], &K[i]);
        for(j=0; j<N[i]; j++)
            scanf("%d ", &input[i][j]);
    }
    for(i=0; i<T; i++)
    {
        End=0;
        printf("Case #%d\n", i+1);
        comb(input[i],set, 0, N[i], K[i], 0, K[i]);
        if(End==0)
            printf("0\n");
    }
    
    return 0;
}

flflds0811 7년 전 1

코드를 자세히 보지 않았지만

해당 문제는 LIS(longest inceasing subsequence) 문제로

해당 문제를 푸는 알고리즘을 공부하신 후에 풀어보시는 것이 좋습니다.

기본적으로 다이나믹 프로그래밍을 사용하는 O(N^2)방식과

다이나믹 프로그래밍과 세그먼트트리를 이용하는 O(NlogN) 방식,

lower_bound를 이용하는 O(NlogN)방식이 있습니다.

해당 알고리즘을 찾아 공부하신 후 문제를 풀어보세요

sium 7년 전 0

감사합니다. LIS라고 처음 들어봐서 잠시 봤는데, 많은 도움이 될거 같네요

xman 3년 전 0

질문 보신 분이 혼동이 있을까봐 알려드리면

이 문제는 LIS를 이용하는 문제가 아니고 Parametric Search를 이용하는 것입니다.

dps2 3년 전 0

보다 정확히는 LIS를 binary search를 이용해 푸는 것이라고 생각합니다.

LIS를 접근하는 방식에는 여러가지가 있는데 가장 대표적인 방법이 O(n^2)인 DP 방법과 O(nlogn)인 binary search 방법이 있습니다.

parameteric search라고 하셨는데 parameteric search를 찾아보면

The basic idea of parametric search is to simulate a test algorithm that takes as input a numerical parameter X, as if it were being run with the (unknown) optimal solution value X* as its input. This test algorithm is assumed to behave discontinuously when X=X*, and to operate on its parameter X only by simple comparisons of X with other computed values, or by testing the sign of low-degree polynomial functions of X.

즉 https://www.acmicpc.net/proble... 중량제한과 같은 문제(무게로 다리를 건널 수 있는지의 여부를 확인하여 무게를 조정하여 최대 무게를 찾는 문제)가 parameteric search를 사용한 것이고, LIS에서 사용하는 search는 binary search로 보는 것이 타당합니다. LIS에서 사용하는 search를 생각해보면 simulate와는 거리가 멀고 search 이후 계속 쓰이는 LIS 배열을 업데이트하기 때문입니다.

저도 초심자이기 때문에 틀린 점이 있을 수 있습니다. 혹시 틀린 부분이 있다면 알려주시면 감사하겠습니다.

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

문제

문제

출처

ICPC

시간 초과....

sium 7년 전 0

flflds0811 7년 전 1

sium 7년 전 0

xman 3년 전 0

dps2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말