본문 바로가기

Longest Increasing Sequence2

[Python]14002. 가장 긴 증가하는 부분 수열 4 (LIS) https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 핵심아이디어는 변경시킨 인덱스를 별도의 배열에 저장하여 역추적 하는 것(v 에 저장 후 역추적). n = int(input()) a = [0]+list(map(int, input().split())) DP = [0]*(n+1) v = [-1]*(n+1) for i in range(1,n+1): f.. 2019. 4. 5.
[Python]11053. 가장 긴 증가하는 부분 수열 (LIS) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 아이디어를 떠올리기 어려웠다. LIS 는 굉장히 중요한 문제이므로 연습이 필요하다. 정답은 부분수열이므로, 특정 시점에서 (i) 에서 맨 앞쪽까지 크기 비교를 수행한 뒤, 가장 큰 길이(DP 값)를 구해서 마지막에 자기자신(+1)을 더한다. 즉 D[i] = max(D[i-1], D[i-2], ... .. 2019. 4. 5.
728x90
반응형

티스토리툴바