글 읽기 - 시간초과 원인을 알려주실 수 있나요...?

osh1795 1년 전 0

input에 랜덤 숫자넣어보고 여러번 확인해보니까 코드는 얼추 맞는거 같습니다.

근데 코드가 1%도 못넘기고 시간초과가 발생합니다.

혹시 어느 부분이 불필요하고 연산을 많이 잡아먹는지 봐주실 수 있을까요?

틀린 부분이 있다면 알려주시면 감사하겠습니다!!

from random import randint
    # 랜덤 input
n = randint(5,10)
nums = []
for _ in range(n):
    nums.append(randint(1,100))
print(nums)

    # input
# n = int(input())
# nums = list(map(int,input().split()))

flag = {-1:-1,0:-1}   # 해당 인덱스를 추가하기 전의 인덱스
dp = [1]*n  # 각 인덱스가 종점일 때의 증가 수열 길이

max_ = 1    # 증가 수열 최대 길이
idx = 0     # 증가 수열 최대 길이 종점
for i in range(1,n):
    max_idx = -1    # 추가할 부분 수열의 종점
    for j in range(i):
        if nums[j] < nums[i]:   # 작은 수 등장
            if dp[i] < dp[j] +1:    # 현재 숫자를 추가했을 시와 비교
                dp[i] = dp[j] +1
                max_idx = j     # 갱신
                if max_ < dp[i]:    # 최대 길이 및 인덱스 갱신
                    max_ = dp[i]
                    idx = i
    flag[i] = max_idx   # 경로 저장
print(max_) 
ans = [idx] # 정답 인덱스 저장
while True: # 경로를 거꾸로 치고 올라가며 확인
    tmp = flag[ans[-1]] 
    if tmp == -1:   # 시작점 도달시 break
        break
    else:
        ans.append(tmp)

while ans:  # 경로 출력
    print(nums[ans.pop()], end=' ')

byeongkeunahn 1년 전 1

O(N²) LIS를 구현하셨습니다. 현재 문제는 적어도 O(N lg N) LIS가 필요합니다. 두 가지 알고리즘이 있습니다. 세그먼트 트리를 기반으로 하는 LIS 알고리즘과, LIS 자체에 특화된 알고리즘입니다.

osh1795 1년 전 0

그럼 새로 작성해야겠네요... 감사합니다!!!

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

문제

문제

출처

ICPC

시간초과 원인을 알려주실 수 있나요...?

osh1795 1년 전 0

byeongkeunahn 1년 전 1

osh1795 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말