코생코사

https://www.acmicpc.net/problem/9251 참고: https://osnim.tistory.com/entry/%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4-LCSLongest-Common-Subsequence-%ED%8C%8C%EC%9D%B4%EC%8D%AC 최장 공통 부분수열, LCS(Longest Common Subsequence) (파이썬)LCS (Longest Common Subsequence)이란? 2개 이상의 문자열에서에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미합니다. LCS은 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나osnim.tistory.comD..

https://www.acmicpc.net/problem/1309 DP를 사용 맨 위의 두 칸을 세 가지 경우로 나눈다- 공백: 두 칸에 아무도 없음- 좌: 왼쪽 칸에 사자 있음- 우: 오른쪽 칸에 사자 있음 만약 n이 1이라면위처럼 세 가지 경우가 있습니다  n이 2인 경우를 보겠습니다 그런데 아래 칸(파란색)의 경우의 수는n=1일 때의 경우의 수와 같습니다  즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다. dp 점화식으로 풀게 된다면# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른..