동적 프로그래밍
2022. 8. 10. 20:53ㆍ대학원 입시/알고리즘
LIS (최장 증가 수열)
https://4legs-study.tistory.com/106
최장 증가 수열 (LIS, Longest Increasing Subsequence)
최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각
4legs-study.tistory.com
O(N^2) - DP 사용
O(N*logN) - DP + 이진탐색 사용
import sys
n = int(input())
S = list(map(int, sys.stdin.readline().split()))
def N_square():
dp = [1] * n
for i in range(n):
for j in range(i):
if S[i] > S[j]:
dp[i] = max(dp[j] + 1, dp[i])
print(max(dp), dp.index(max(dp)), dp)
def N_logN():
dp = [0]
for i in range(n):
if S[i] <= dp[-1]:
start = 0
end = len(dp)-1
while start < end:
mid = (start + end) // 2
if dp[mid] < S[i]:
start = mid + 1
elif dp[mid] > S[i]:
end = mid
else:
end = start = mid
dp[end] = S[i]
else:
dp.append(S[i])
print(len(dp) - 1)
N_square()
N_logN()
백준 1149 RGB house
점화식 세우기
i-2, i-1, i 관계식으로 DP table 만들기
N = int(input())
color = [list(map(int, input().split())) for _ in range(N)]
dp = [[1000] * 3 for _ in range(N)]
dp[0] = color[0]
for i in range(1, N):
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + color[i][0]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + color[i][1]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + color[i][2]
print(min(dp[-1][0], dp[-1][1], dp[-1][2]))
백준 1932 정수 삼각형
왼쪽, 오른쪽, 가운데 위치를 구분해서 DP table 만들기
N = int(input())
triangle = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * i for i in range(1, N + 1)]
for i, tri in enumerate(triangle):
if i == 0:
dp[0][0] = triangle[0][0]
continue
elif i == 1:
dp[1][0] = dp[0][0] + triangle[1][0]
dp[1][1] = dp[0][0] + triangle[1][1]
continue
for j, t in enumerate(tri):
if j == 0:
dp[i][0] = dp[i-1][0] + t
elif 1 <= j < i:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + t
elif i == j :
dp[i][j] = dp[i-1][j-1] + t
print(max(dp[-1]))
고수의 풀이
def solution():
import sys
n = int(input())
triangle =[]
for _ in range(n):
triangle.append(list(map(int, sys.stdin.readline().rstrip().split())))
accum = []
for i in range(n):
accum = [max(a+c, b+c) for a,b,c in zip([0]+accum, accum+[0], triangle[i])]
print(max(accum))
solution()
편집거리 알고리즘 https://joyjangs.tistory.com/38
[Python] 편집 거리 알고리즘 ( Edit Distance )
[Python] 편집거리 알고리즘 편집거리 알고리즘은 두 문자열의 유사도를 판단하는 알고리즘이다. 수정, 삽입, 삭제 기능이 있다고 할 때 몇 번의 동작이 필요한지 측정한다. 문자열 내에서 위치 변
joyjangs.tistory.com
dp = [[0] * (len(str2)+1) for _ in range(len(str1) + 1)]
for i in range(1, len(str1)+1):
dp[i][0] = i
for j in range(1, len(str2)+1):
dp[0][j] = j
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
return dp[-1][-1]