회문(Palindrome)

1. 문제

We define a palindrome to be a sequence of characters that reads the same backward

as it does forward.

 

For example,

“tacocat” and “12221” are palindromes, but, “tacocats” and “8675” are not.

 

We define a subsequence to be a sequence formed by copying a contiguous section of

elements from sequence and deleting 0 or more characters from it.

 

Walter wants to improve his understanding of strings.

So he asks Monica to give him string problem.

She creates a string, s , of ‘n’ lowercase English letters and tells him to find the length of the longest subsequence of ‘s’ such that the subsequence is also a palindrome.

 

Complete the longest palindrome function in the editor below.

 

It has two parameters:

1. An integer, ‘n’, denoting the number of characters in Monica’s string.

2. A string, ‘s’ , denoting Monica’s string.

The function must return an integer denoting the length of

the longest Palindrome subsequence of ‘s’.

​

Input Format

Locked stub code in the editor reads the following input stdin and

passes it to the function:

The first line contains an integer, ‘n’ , denoting the number of characters

in Monica’s string.

The second line contains a string, ‘s’ , denoting Monica’s string.

 

Constraints

1. 1 <= ‘n’ <= 5000

2. String, ‘s’ , consist of lowercase English alphabetic letters.

 

Output Format

The function must return an integer denoting the length of

the longest Palindrome subsequence of ‘s’.

This is printed to stdout by locked std.

​

Sample Input 0

           2

           ​​ba

Sample Output 0

           1

 

Explanation 0

The only Palindrome subsequence of ‘s’ = “ab” are “a” and “b”.

As both of these have length 1, we return 1 as our answer.

 

Sample Input 1

           3

           aaa

Sample Output 1

           3

 

Explanation 1

The string s = “aaa” is already Palindrome so we return 3 as our answer.

 

Sample Input 2

           6

           banana

Sample Output 2

          5

 

Explanation 2

The longest Palindrome subsequence of ‘s’ = “banana” is “anana”, so we return 5

as our answer.

 

2. 문제 분석

탐색은 다음과 같이 할 것이다. 이 탐색을 수행할 함수의 이름은 PalindromeByDFS라 한다.

아래의 그림은 PalindromeByDFS함수의 호출 스택을 나타낸 것이다. ( 재귀 함수의 호출)

붉은색 숫자가 호출되는 순서이다.

초록색 화살표와 하늘색 화살표는 탐색할 인덱스의 위치들이다.

문자열 "aba"는 회문이다.

PalindromeByDFS함수에서는 두 탐색 인덱스를 기준으로 현재 탐색할 문자열이 회문인지를 체크한다.

체크를 해서 회문이라면 이 때의 문자열과 문자열의 길이를 저장하면 된다.

다만, 조건이 회문이라고 무조건 저장하는 것이 아닌, 그 이전에 저장한 회문의 문자열의 길이를 비교해서

현재의 회문 문자열의 길이가 더 길때만 저장하자.

3. 구현

프로그램 실행결과1

프로그램 실행결과2

프로그램 실행결과3

4. 소스 파일

main.c

0.00MB

5. 수정할 사항

위의 그림에서 보면,  호출 순서 4와 6이 같은 위치를 중복으로 탐색하는 것을 볼 수 있다.

이에 대해, 메모이제이션 기법을 이용해서, 중복으로 탐색하는 것을 막을 수 있다.

임시 방편으로 DT라는 배열을 하나 전역변수로 두겠다.

배열의 크기는 임의로 정해주었는데, 이는 나중에 입력 배열의 길이만큼 동적할당해서

이차원 배열로 만들어서 쓰면 될 것 같다.

위의 변수는 탐색하는 함수인 PalindromeByDFS함수에서 쓰인다.

프로그램 실행결과1

프로그램 실행결과2

프로그램 실행결과3

6. 소스 파일

main.c

0.00MB

 

위에서 DFS를 구현했다면 아래에서는 BFS로 구현한 내용이다.

designatedroom87.tistory.com/73

회문(Palindrome)