글 읽기 - 10818 시간초과 이유를 모르겠습니다 ㅠ

yonggari0821 1년 전 0

아래와 같이 짜 보았는데 시간초과로 뜹니다 ㅠㅠ

그 이유를 모르겠어서 질문드립니다!

#include <stdio.h>

int main () {
    
    int N,rn,i,j;
    scanf("%d", &N);
    const int a = N;
    int num[a];
    int rank[a];
    
    for (i=0;i<a;i++) {
        scanf("%d ", &num[i]);
    }
    
    for (i=0;i<a;i++) {
        rn=0;
        for (j=0;j<a;j++) {
            if (num[i] < num[j]){
                rn++;
            }
        }
        
        rank[rn] = num[i];
        
    }
   
    printf("%d %d", rank[a-1], rank[0]);
    return 0;
    
}

dldyddlwl 1년 전 2

// 정말 잘 해주셨는데요!!!!!!
// 왜 시간초과가 뜰까요? => 문제에서 의도한 시간보다 더 오래걸렸기 때문입니다.
// 그러면 어느 부분이 시간을 그렇게 쓰는건지 알아봐야겠죠?

// 자, 주로 반복문을 보면 시간을 대략 알 수 있습니다. 

    for (i=0;i<a;i++) {        // 바깥의 for 루프 => 총 a번을 돕니다.
        rn=0;
        for (j=0;j<a;j++) {        // 안쪽의 for 루프 => 총 a번을 돕니다.
            if (num[i] < num[j]){
                rn++;
            }
        }      
        rank[rn] = num[i];
        
    }

// 결과적으로 a * a = a^2 번을 돌게 됩니다.

// 생각해봅시다. 반복횟수를 더 줄일 수 있을까요?
// 예를 들어서, 키가 가장 큰 사람과 가장 작은 사람을 찾는다고 해봅시다.

// 160 158 162 196 210 200 152 156    의 키를 가진 사람들이 있다고 할 때, 질문자님은 어떻게 찾을건가요?

// 쭉 보면서 가장 큰 사람을 찾겠죠? 그러면서 동시에 가장 작은 사람도 찾을 겁니다.
// 이를 수행하기 위해서 각 사람들을 몇번씩 봐야할까요? 까먹지만 않는다면 각각의 사람들을 1번만 봐도 충분하겠죠?

// 스포일러 (아래는 예시 코드~)
//
//
//
//
//
//
//
//
//
//
//
//
//
// aa

// a번의 루프로 최소와 최대를 조사할 수 있음!!
for(int i = 0; i < a; i++){
    if(max < num[i]){   
        max = num[i]
    }
    if(min > num[i]){
        min = num[i];
    }
}

yonggari0821 1년 전 0

답변 정말 너무 감사합니다!!

컴퓨터 자체적으로 문제 해결에 걸리는 시간(Big Ω라고 하나요?)이

문제에서 의도한 것보다 길어서 그런 거라는 지적이 제 코드 문제점 이해하는 데 정말 도움이 되었습니다!

혹시 백준의 모든 문제가 이런식으로 그 시간을 고려하지 않고 풀면 틀리게 되는지(그래서 항상 가장 시간이 적게 걸리는 방식으로 풀어야 하는지) 궁금한데 이 부분도 아시나요?

dldyddlwl 1년 전 1

네, 아무래도 알고리즘이라는 것이 정확성도 중요하지만 그만큼 효율성도 중요하니깐요!

그렇다고해서 모든 문제들의 시간제한이 그렇게 빡빡하지만은 않습니다. 어떤 문제는 시간이 널널한 편이라, 생각나는 답을 그대로 제출해도 정답이 되는 경우도 있지만,

또 어떤 문제는 머리를 쥐어짜서 어떻게든 시간을 줄여야 하기도 합니다. 그래서 사실, 출제자의 재량(?)인 부분입니다.

역시 가장 좋은건 모두 경험해보는 것이겠지요? 처음에는 일단 떠오르는 대로 느리더라도 대신 정확하게, 시간초과가 된다면 조금 더 시간을 줄여보고, 혹시나 정답이더라도

다른 사람들의 코드등을 참고해서 여기서 시간을 더 줄일 수 있는 지를 계속 고민해보신다면 분명 큰 도움이 되실거라고 생각합니다!! 하하 파이팅하세요!

yonggari0821 1년 전 0

정말 너무 친절한 답변 감사합니다!!!!!

꼭 복 받으세요!!

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

문제

문제

출처

ICPC

10818 시간초과 이유를 모르겠습니다 ㅠ

yonggari0821 1년 전 0

dldyddlwl 1년 전 2

yonggari0821 1년 전 0

dldyddlwl 1년 전 1

yonggari0821 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말