글 읽기 - 프로그램 실행시간 계산 방법

seok9311 9년 전 0

가끔 시간제한 걸리는 문제들이 있어서 시간초과가 뜰때마다 좌절하면서 제가 직접 최악의 데이터들을 나름대로 만들어보며 수행시간을 측정하는데 문득 궁금해진게 있는데요...

시간 계산할때 출력하는 시간도 계산되나요?

예를들어 시간제한이 1초이고 출력해야할 데이터가 1~50000까지라면 아무런 알고리즘없이 단순히

for(i=1;i<=50000;i++) printf("%d\n",i);

만 해도 1초가 넘는데...

뭔가 설명이 제대로 안되는거 같은데 음....

한마디로 정리하면 시간계산할때 어디부터 어디까지를 측정하는지....

이 문제는 그냥 시간초과당한 문제 예시입니다...

#include <stdio.h>

typedef int element;
typedef struct HeapType{
    element heap[100000];
    int size;
}HeapType;

void init(HeapType *h){
    h->size=0;
    return;
}

int is_empty(HeapType *h){
    return (h->size==0);
}

void insert(HeapType *h, element data){
    int i;
    i=++(h->size);
    while(i!=1 && h->heap[i/2]>data){
        h->heap[i]=h->heap[i/2];
        i=i/2;
    }
    h->heap[i]=data;
    return;
}

void removeh(HeapType *h){
    int child, parent, tmp;
    printf("%d\n",h->heap[1]);
    tmp=h->heap[h->size--];
    parent=1;
    child=2;
    while(child<=h->size){
        if(child<h->size && h->heap[child]>h->heap[child=1])
            child++;
        if(tmp<h->heap[child])
            break;
        h->heap[parent]=h->heap[child];
        parent=child;
        child*=2;
    }
    h->heap[parent]=tmp;
    return;
}

int main(){
    int i,n,num;
    HeapType heap;
    init(&heap);
    
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&num);
        if(num==0){
            if(is_empty(&heap))
                printf("0\n");
            else
                removeh(&heap);
        }
        else
            insert(&heap,num);
    }
    return 0;
}

pichulia 9년 전 1

일단 채점시에는 프로그램의 시작부터 끝까지의 시간을 측정하니깨...입력(scanf)과 출력(printf)의 시간도 포함되겠죠...

근데 좀 적당히 크고 정상적인 프로그램이라면 입출력보단 중간 계산과정이 미치는 영향이 훨씬 크기 때문에 무시하는게 정신건강에 좋죠ㅋㅋ

그리고 저 코드...

제가 보기엔 36번째 줄이 문제인거같네요

seok9311 9년 전 0

그럼 결국 printf와 scanf 부분은 무시해도 된다는 뜻이군요? ㅎㅎ

그리고 36번째줄 지적 감사합니다.......(민망)

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

문제

문제

출처

ICPC

프로그램 실행시간 계산 방법

seok9311 9년 전 0

pichulia 9년 전 1

seok9311 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말