수열이 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 동적 프로그래밍 알고리즘의 대표적인 문제입니다.
이 문제는 특정 인덱스에서 증가하는 부분 수열을 구해놓은 dp 리스트를 이용해 현재 인덱스보다 앞의 상황에서 증가하는 부분 수열의 최대 길이를 저장해둠으로써 연산 횟수를 줄였습니다.
def main():
N = int(input())
arr = list(map(int, input().split()))
dp = [1] * N
for i in range(N):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
if __name__ == "__main__":
main()
동적 프로그래밍은 간단하게 약간의 메모리를 더 사용해서 속도 효율을 높이는 방법입니다.
한번 계산했던 것은 다시 계산하지 않고 저장되어있던 값을 사용합니다.
동적 프로그래밍은 주로 아래와 같은 상황에서 사용합니다.