120151 [백준] 12015번 파이썬 - 가장 긴 증가하는 부분 수열 2 문제 첫 코드n = int(input())lst = list(map(int,input().split()))answer = 0dp = [1] * (n)for i in range(0,n): dp[i] = 1 tmp = 0 for j in range(i+1,n-i): if lst[i] tmp: tmp = lst[j] dp[i] += 1print(max(dp)) 다이나믹 프로그래밍을 사용하여 풀었고(LIS 알고리즘), 시간초과가 났다.문제 제목만 보고 입력 조건을 확인하지 않았다.. 위 코드의 시간복잡도를 계산해보니첫 for문에서 n, 두번째 for문에서 i부터 n까지 돈다고 해도결국 시간복잡도는 O(N^2)가 된다. 따라서 시간복잡도를 줄일.. 2024. 6. 27. 이전 1 다음
