LPS 문제 풀이 및 C언어구현 코드

목차

1. 문제 정의
2. recurrence relation 증명 및 설명
3. 해당 recurrence relation을 DP로 해결하기 위한 memoization 의 사용법과 sequence 길이를 구한 후 실제 sequence를 출력하는 알고리즘에 대한 설명
4. pseudocode
5. time complexity 구하기
6. 출력결과예시

본문내용

1) 문제 정의
주어진 sequence에서 가장 긴 palindromic한 subsequence를 출력한다. 여기서 palindromic은 왼쪽에서부터 읽으나 오른쪽에서부터 읽으나 동일하게 읽히는 것을 의미한다. 예시로 다음의 sequence가 있다하자.
여기에서 subsequence A B B A는 palindromic하다. 그리고 여기서 가장 긴 palindromic은 A B G G B A 이다.
여기서 sequence는 사용자가 그 길이와 해당 요소를 입력하고 출력은 선택된 subsequence의 길이와 그 해당 요소를 출력한다. 그리고 해당 알고리즘은 O(n^2) 안에 실행되어야 한다.

2) recurrence relation 증명 및 설명
L(i, j) 를 ai, ... ,aj로 이루어진 sequence에서 가장 긴 palindromic 한 subsequence의 길이라 하자 그럴 경우 L(i, j)는 다음의 recurrence relation을 만족하게 된다.
첫 번째의 경우는 입력된 sequence의 길이가 1인 경우이다. 예로는 subsequence 가 1 2 1인 경우로 양 옆의 1 1을 지우고 2일 때 앞으로 읽으나 뒤로 읽으나 그 읽힘이 동일하기에 sequence 에 포함한다. 따라서 1을 추가시킨다.
두 번째의 경우 입력된 sequence 의 길이가 2이고 두 개의 값이 같은 경우이다. 이 때는 이것만으로 subsequence 가 만족이되고 sequence 가 끝남으로 2를 반환해준다.

참고 자료

없음