글 읽기 - 시간초과 관련 - 시간 복잡도 계산 관련 질문 드립니다.

jayheo91 3년 전 0

안녕하세요,

문제를 풀다가 문득 의문점이 생겨서 질문드립니다.

DFS로 풀면 쉽게 해결될 문제인 것은 알고 있지만, 실전 코딩테스트에서 과연 이걸 생각할 수 있을까? 라는 의문이 들어 브루트포스로 한번 문제를 해결해 보았습니다.

제가 단순히 생각해 보았을 때, 500*500이 맥시멈이고 모든 점을 계산한다면 19 * 4 = 76의 경우의 수가 나와서 총 76 * 500 * 500 = 1800만 이라 생각하고 문제를 풀이하여 보았습니다.

하지만 시간 초과로 fail 되었고, 속도가 빠른 PyPy3으로 진행하니 pass 되었습니다.

일반적으로 맥시멈 경우의 수가 1억인 경우에만 시간 관련해서 문제가 생길 것으로 생각하고 문제를 풀었는데.. 어디선가 속도 저하가 이루어 지는 것 같습니다.

아래와 같은 단순한 코드를 사용할 때, 문제 연산을 발목잡는 부분이 어느 부분일지 알 수 있을까요?

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())

mat = list()
tet_shape = [list() for x in range(5)]
max_value = 0
# 일자형
tet_shape = [
    [(0,0), (0,1), (0,2), (0,3)],
    [(0,0), (1,0), (2,0), (3,0)],
    [(0,0), (0,1), (1,1), (1,0)],
    [(0,0), (0,1), (0,2), (1,0)],
    [(0,0), (1,0), (1,1), (1,2)],
    [(0,0), (1,0), (2,0), (2,1)],
    [(0,1), (1,1), (2,1), (2,0)],
    [(0,0), (0,1), (0,2), (1,2)],
    [(0,0), (0,1), (1,0), (2,0)],
    [(0,0), (0,1), (1,1), (2,1)],
    [(0,2), (1,0), (1,1), (1,2)],
    [(0,0), (1,0), (1,1), (2,1)],
    [(0,1), (0,2), (1,0), (1,1)],
    [(0,0), (0,1), (1,1), (1,2)],
    [(0,1), (1,1), (1,0), (2,0)],
    [(0,0), (0,1), (0,2), (1,1)],
    [(0,1), (1,0), (1,1), (1,2)],
    [(0,1), (1,0), (1,1), (2,1)],
    [(0,0), (1,0), (2,0), (1,1)]
]

for _ in range(n):
    mat.append(list(map(int, sys.stdin.readline().rstrip().split())))

for row_index in range(n):
    for elem_index in range(m):
        for coords in tet_shape:
            value = 0
            for coord in coords:
                tmp_x = row_index + coord[0]
                tmp_y = elem_index + coord[1]
                if tmp_x >= n or tmp_y >= m:
                    value = 0
                    break
                else:
                    value += mat[row_index + coord[0]][elem_index + coord[1]]
            max_value = max(value, max_value)

print(max_value)

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

문제

문제

출처

ICPC

시간초과 관련 - 시간 복잡도 계산 관련 질문 드립니다.

jayheo91 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말