가장 긴 증가하는 부분 수열
풀이 시간: 3시간
결과: 실패
접근방법
10 20 10 30 20 50
처음 문제를 봤을 때, 단순히 쉽게 중복되는 부분만 뺀 집합 형태에서 원소수를 세면 될 줄 알았다.
그래도 쉽지 않았다. 계속해서 반례케이스를 만들어 검증하는 과정에서 접근 방법 조차 잘 못 됐다는것을 인지하고 다시 처음부터 구상하기 시작했다.
import sys
n = int(input())
arr = []
arr =list(map(int,(sys.stdin.readline().split(' '))))
dp = [0]*n # 카운팅할 배열 생성
dp[0]=1 # 무조건 1이상이니까 1을 누적
mv = 0 # mv 최대값을 저장할 변수
for i in range(1,len(arr)): #1부터 반복
if arr[i] > arr[i-1] : #현재 원소와 이전 원소를 비교하여 현재원소가 큰지 비교 and 최대 값과 비교
dp[i] = 1 # dp 배열 현재 인덱스에 카운팅
mv = arr[i] # 현재 배열을 최대 배열로 설정
else:
j = i-1
while j >= 0: # arr[i] > arr[j] # 거꾸리로 반복문 돌며 j가 0일때까지 반복
if arr[j] < arr[i] and arr[i] > mv: # i가 j보다 크고, mv보다 크면
dp[i]= 1 # dp 카운팅
break # 반복문 종료
j-=1
print(sum(dp)) # dp 카운팅에 총 개수 출력
코드 설명
10 부터 50까지 for문 반복으로 i와 i+를 비교하고 다시 그 간격만큼 반복문을 돌며 DP라는 배열에 카운팅 했다.
대충 반례로 설정한 테스트 값들도 다 맞고 돌린결고ㅏ.... 실패..
더 이상의 아이디어는 떠오르지 않아 gpting 해버렸다..
GPT 개선코드
import sys
import math
import time
start = time.time()
math.factorial(100000)
#n = int(input())
arr = [10,1,3,2,4,3,5,4,6,5,7]
dp = [1]*len(arr)
for i in range(len(arr)):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i],dp[j]+1)
print(max(dp))
end = time.time()
print(f"{end - start:.5f} sec")이럴수가.. 이중 for문으로 작성하는 것이였던 것이였던 것이였다
문제에게 배신감을 느끼며 코드를 분석해보니 핵심은. 이중 for문이지만 nlogN
2번째 반복문은 i 값을 기준으로 반복되기 때문에 최악에 경우에도 O(NlogN) 인 것이다...
ㅁㅊ
여하튼 이런식으로 반복을하며, [i][j]의 크기를 비교 후 dp에 누적. but j+1번째와 비교하여 누적된 더큰 값이 있을경우를 비교해서 넣기 위해 max함수로 i 또는 j+1 중 최대값을 비교하여 dp[i]번째에 값 변경.
아래 이미지와 같이 분기별로 i와 j를 반복하며, 전체 배열을 순회 할 것이다.
배열을 비교하고 dp에 누적하는 것은 맞았지만
결정적으로 DP에 누적하는 방식과 최대 값을 찾는 등 역시 디테일한 부분이 다소 부족했다.
쓰기에 따라 모든 이중 for문이 n^2 아닌 것을 깨닫게 되었으며, 좋은 문제였다.
일단함