기록과 정리의 공간

백준 9251번 : LCS(문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍(DP), LCS 난이도 : 하 소스코드 import sys x = sys.stdin.readline().rstrip() y = sys.stdin.readline().rstrip() D = [[0] * (len(y)+1) for _ in range(len(x)+1)] for i in range(1, len(x)+1): for j in range(1, len(y)+1): if x[i-1] == y[j-1]: D[i][j] = D[i-1][j-1] + 1 else: D[i][j] = max(D[i][j-1], D[i-1][j]) print(D[len(x)][len(y)]) 설명 최장 공통 부분 수열(LCS..

백준 11053번 : 가장 긴 증가하는 부분 수열(문제 링크) 사용 언어 : 파이썬(Python) 문제 유형 : 동적 프로그래밍(DP), LIS 난이도 : 하 소스코드 import sys n = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) D = [1] * n for i in range(1, n): for j in range(0, i): if array[j] < array[i]: D[i] = max(D[i], D[j] + 1) print(max(D)) 설명 가장 긴 증가하는 부분 수열(LIS) 문제는 전형적인 DP문제이다.(반드시 알아두기!) 수열의 크기가 n일 떄, 기본적인 DP알고리즘으로 O(n^2)에 해..