글 읽기 - 시간 초과 질문 드립니다

rlathdwls2 4년 전 0

먼저 질문 읽어 주심에 감사드립니다.

퇴각 검사를 위해 돌을 새로운 위치에 놓을 수 있는지 검사하는 함수를 2가지로 만들었습니다.

possibleA는 방향을 배열에 저장한 후 반복문을 돌려 공격당할 수 있는 위치인지 검사하는 것이고

possibleB는 방향별로 반복문을 3번 돌려 공격당할 수 있는 위치 인지 검사하는 함수 입니다.

코드의 표현이 다를 뿐 수행하는 시간은 두개 다 동일하다고 생각했습니다.

하지만 possibleA는 시간초과가 발생하고 possibleB는 AC를 받습니다.

동일하다고 생각하는 함수중 왜 어떤것은 맞고 어떤것은 틀린지 알고 싶고

향후 반복문 코드를 작성할때 어떤 방식으로 해야 효율적으로 할 수 있는지 팁도 얻고 싶습니다.

긴 글 읽어 주심에 감사드립니다.

#include <iostream>
#include <vector>
#define MAX 15

using namespace std;

int board[MAX][MAX];
int n, num;


bool inRange(int y, int x){
    return 0<=y && y < n && 0<=x && x < n;
}

bool possibleA(int y, int x){
    int dx[5] {-1, 0, 1};
    int dy[5] {-1, -1, -1};
    
    for(int i = 0 ; i < 3 ; i++){
        int ny = y, nx = x;
        while(inRange(ny, nx)){
            if(board[ny][nx]==1)
                return false;
            ny += dy[i];
            nx += dx[i];
            
        }
    }
    return true;
}

bool possibleB(int y, int x){
    for(int ny = y, nx = x; ny>=0&&nx>=0 ; ny--, nx--){
        if(board[ny][nx] == 1)
            return false;
    }
    
    for(int ny = y, nx = x; ny>=0&&nx<n ; ny--, nx++){
        if(board[ny][nx] == 1)
            return false;
    }
    
    for(int ny = y, nx = x; ny>=0&&nx>=0 ; ny--){
        if(board[ny][nx] == 1)
            return false;
    }
    return true;
}


void drop(int y){
    if(y == n){
        num+=1;
        return;
    }
    
    for(int x = 0; x < n ; x++){
        if(possibleB(y, x)){
            board[y][x] = 1;
            drop(y+1);
            board[y][x] = 0;
        }
    }
}


int main(int argc, const char * argv[]) {
    num = 0;
    cin>>n;
    drop(0);
    cout<<num<<endl;
    
    return 0;
}

slah007 4년 전 3

직접 컴파일해서 실행해보니 실행 시간이 1.5~2 배 정도 차이가 나는데, 사소한 차이가 시간초과인지 아닌지를 결정한 것 같습니다. 고칠 점을 굳이 꼽자면,

1. 같은 내용이라도 함수 호출(inRange(y,x))을 하는 것보다는 하지 않는 편이 훨씬 빠릅니다. 단순한 함수의 경우 매크로 (#define inRange(y,x) (0<=y && y < n && 0<=x && x < n))를 사용하면, 함수를 사용하지 않고 풀어 쓰는 경우와 동일한 동작 시간을 냅니다.

2. 배열을 선언하고 초기화하는 데에도 그 크기에 비례하는 시간이 소요됩니다. 이 경우에는 함수를 n번밖에 호출하지 않는데다가 배열 크기가 작아서 별로 상관없지만, 반복해서 같은 변수를 선언하는 함수가 여러 번 호출되면 상대적으로 느려집니다. 이런 경우 지역변수 대신 전역변수를 사용하는 편이 낫습니다.

3. 상수 값(1,0,-1)을 사용하는 것이 메모리 내의 값 참조(dx[i], dy[i])보다 훨씬 빠릅니다. 물론 제한시간이 여유롭다면 편의성과 가독성을 위해 상수보다는 변수를 사용하는 것이 바람직합니다.

이런 최적화는, 문제를 맞으신 뒤에 잘 짜여진(실행 시간도 빠르고 가독성도 좋은) 다른 분의 코드를 보는 것이 도움이 많이 됩니다.

rlathdwls2 4년 전 1

제가 몰랐던 내용을 친절 하게 잘 알려주셨네요.

1. 함수 호출시 시간 소모 => 메크로 사용

2. 반복된 배열 변수 선언과 사용에도 시간 소모 => 전역 변수 사용

3. 메모리 값 참조 시간 소모 => 상수 사용

이 3부분을 댓글을 보고 배워 갑니다.

가독성도 좋고 빠른 코드를 찾아 접목 시켜 보는 것도 해봐야 겠습니다.

친절한 답변 정말 감사드립니다.

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

문제

문제

출처

ICPC

시간 초과 질문 드립니다

rlathdwls2 4년 전 0

slah007 4년 전 3

rlathdwls2 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말