computational thinking_03

1.LIS

1) 부분 수열

길이가 n인 수열이 있다.

이 수열이 부분 수열이란 이 수열을 구성하는 수으 순서는 유지한 채 몇개으 ㅣ수를 제거해서 얻을 수 있는 수열들을 의미한다.

예를 들어 1324라는 수열의 부분수열은 다음과 같다.

1 / 3 / 2 / 4 / 13 / 12 / 14 / 32 / 34 / 23 / 132 / 134 / 124 / 324 / 1324

123은 원래 수열에서 순서를 바꿔야 만들 수 있기 때문에 부분 수열이 아니다.

 

2)가장 긴 증가하는 수열 : LIS

앞에서 1324의 부분수열을 모두 구했는데 다시 나열해보면 124 / 134가 길이가 3으로 가장 길고 오름차순 수열의 특징을 가지고 있다.

 

2.2차원 단순점화식

1) 2차원 점화식의 문제 컨셉

-1차원 점화식에서 사용했던 표가 두 줄 혹은 세 줄 정도 나와서 서로 영향을 주는 경우

-가로 줄과 세로 줄이 명확히 의미가 있는 경우

=>문제에서 요구하는 값이 둘 이상일 경우에 나오는데, 보통 어떤 두 문자열을 비교하는 문제나 "~인 것들 중 ~의 조건을 만족하는 것의 최댓값을 구하라" 같은 조건이 둘 이상 달린 경우에 나오게 된다.

3.LCS

1)부분 문자열

-어떤 문자열의 부분 문자열은 이 문자열에서 문자의 순서를 바꾸지 않고 몇개를 지워서 만들 수 있는 문자열을 말한다.

 

2)가장 긴 공통 부분 문자열

-두 문자열 A, B가 주어질 때, A의 부분 문자열이면서 B의 부분 문자열인 문자열 중 가장 긴 것의 길이를 구하는 문제다.