글 읽기 - 이 코드가 O(N^2) 코드인지 궁금합니다

dusrlf13 3년 전 0

입력된 값을 array 리스트에 저장하고 첫번째 인덱스부터 모든 증가수열을 따져본 뒤 현재의 최댓값보다 해당 케이스의 길이가 길다면 갱신해주는 방식으로 코드를 짰는데 시간 초과가 나버리네요...

제 생각에 이 코드가 가지는 시간 복잡도는 N개의 입력중에서 N-1개의 남은 요소들을 검사하니 최대 O(N^2)라고 생각이 되는데 맞는지 궁금합니다.
또한 DP적 방법을 통해 문제를 해결하려면 어떻게 해야 할지 조언을 구하고 싶습니다 ㅠㅠ

반례는 거의 다 맞는 것 같습니다...

N = int(input())

array = list(map(int, input().split()))
temp_list = list()

count = 0

for i in range(N):
    if i != N-1:
        for j in range(i+1, N):
            temp_list.append(array[i])
            for k in range(j, N):
                if array[k] > temp_list[-1]:
                    temp_list.append(array[k])
            temp = len(temp_list)
            if count <= temp:
                count = temp
            temp_list.clear()
    else:
        temp_list.append(array[i])
        temp = len(temp_list)
        if count <= temp:
            count = temp
        temp_list.clear()
print(count)

azberjibiou 3년 전 0

3중 for문이면 N^3 아닌가요?

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

문제

문제

출처

ICPC

이 코드가 O(N^2) 코드인지 궁금합니다

dusrlf13 3년 전 0

azberjibiou 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말