[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.
[Python]15990. 1,2,3 더하기 5
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1차원의 DP로 풀 수 있긴 한데.. 시간이 매우매우 많이 걸린다..!! 문제 조건에 따르면 끝 자리 수와 비교하여 다를때만 연산을 해줘야 하기 때문. 따라서 2차원 DP 를 이용해서 조건을 쪼개본다. DP[i][1] = DP[i - 1][2] + DP[i - 1][3] # 현재 1은 1단계 전의 2 또는 3 에 붙을 수 있다. DP[i][2] = DP[i - 2][1] + DP[i - 2][3] # 현재 2은 2단계 전의 1 또는 3 에 붙을 수..
2019. 4. 3.
