미새문지

피보나치2 피보나치를 재귀방식이 아닌 DP방식으로 풀기(동적 프로그래밍) import sys def fibo(n): list = [0, 1] + [0]*(n-1) for i in range(2, n+1): list[i] = list[i-1] + list[i-2] return list[n] n = int(sys.stdin.readline()) print(fibo(n)) 01타일 1또는 00만을 이용해서 n개의 타일을 깔수있는 경우의 수를 구하기(동적 프로그래밍) import sys n = int(sys.stdin.readline()) pibo = [0, 1] m1 = 0 m2 = 0 i = 0 while i != n: m1 = pibo[0] + pibo[1] m2 = pibo[1] pibo[0] = m2 ..

LCS(Longest Common Subsequence) 공통 부분 문자열 중 가장 길이가 긴 문자열을 말하는 ‘최장 공통 부분 수열’이라고 한다. LCS는 최장 공통 문자열이라고도 불리는데 그 차이는 최장 공통 부분 수열은 문자열 안의 공통된 문자를 다 구한다 최장 공통 문자열은 문자열 안의 공통된 문자 중 연속된 문자를 구한다. 다이나믹 프로그래밍(DP)방식으로 구현된다. ​ LCS - Substring(최장 공통 문자열) 두 문자열을 비교하는 표인데 이 때, 반드시 두 문자열의 가장 앞 칸은 0으로 해야 한다. 만약 두 문자열 중 어느 것이라도 첫 번째 문자가 일치하면 그 좌표의 -1 좌표에서 값을 참조해야 하는데 [0, 0]이면 앞 칸이기 때문에 음수로 참조하게 되고 에러가 발생한다. 최장 공통 ..