[알고리즘/DP/개념] 팰린드롬

Panlindrom

똑바로 읽으나 , 거꾸로 읽으나 똑같은 글자를 Panlindrom 우리나라 말로는 회문이라고 한다.

예를들어 , 주황색 방향으로 읽든(정방향) ,파랑색 방향(역방향)으로 읽든 "기러기"로 읽힌다.

 

팰린드롬이 현실생활에?!

1. 지폐수집

지폐 수집계에서는 RADAR라고 부르는데, 일반 화폐보다 조금 더 가치가 있다고 한다. 참고로, 1가지 숫자로만 되어있으면 "솔리드"라고 부르는데, "9999999"로 되어있는 지폐가 있다면 보존을 잘 해놓자. 약 100만원의 이상의 가치를 가지고 있다고 한다.

 

2. 염기서열

생명과학에서 DNA가 이루는 염기서열을 분석할 때, 특정 염기배열을 나타내는 개념으로 쓰인다고 합니다.(

 

팰린드롬 확인하기

 

팰린드롬을 확인하는 제일 직관적인 방법은, 문자열을 뒤집어 보는거다. 코드로 나타내보자.

 

Flow chart

1. 문자열을 뒤집는다.
2. 뒤집은 문자열과 원래 문자열을 비교해준다.

문자열을 뒤집는 방법은 파이썬에서 내장함수로 구현되어 있기도 하고, slice기능을 통해서 간편하게 구현할 수 있지만,  여기서는 반복문 1개를 이용해서 뒤집어 보겠다.

 

import sys
input= sys.stdin.readline

words=input().rstrip()


def Is_Panlindrom():
    str_reverse=""
    for word in words:
        str_reverse=word+str_reverse
    for i in range(len(words)):
        if words[i] !=str_reverse[i]:
            return False
    return True

if Is_Panlindrom():
    print("This is Panlindrom")
else:
    print("NOpe!")

 

문자열을 뒤집지 않고, 반복문을 가지고 앞/뒤에서 한칸씩 줄이고/늘리는 투포인터 개념을 이용해서도 풀 수 있을것 같다.

 

Flow chart

1. 앞,뒤에서 하나씩 체크를 해준다, 이때 반복은 start와 end가 서로 만날때 까지로 설정해준다.
2. 앞,뒤 문자가 같으면 그대로 진행하고, 다르다면 팰린드롬이 아니므로 return False를 해준다.

import sys
input =sys.stdin.readline

words=input().rstrip()

def Is_panlindrom():
    s=0
    e=len(words)-1
    while s<e:
        if words[s] !=words[e]:
            return False
        s+=1
        e-=1
    return True

if Is_panlindrom():
    print("Yes")
else:
    print("NO")

여기까지가 그래도 선형적인 풀이방법이라고 볼 수 있다. 하지만, 선형적인 풀이는 직관적이라는 장점이 있지만, 컴퓨터 입장에서는 그다지 효율적이지 못한 풀이방법이다. 어떻게 Panlindrom을 잘 풀 수 있을까?

 

팰린드롬 "효율적"으로 확인하기

 

이 풀이는 팰린드롬의 정의를 새롭게 한다. 처음에는 이게 무슨 소리인가 싶어도 따라오면 이해가 자연스럽게 된다.

여기에 ABCBA라는 팰린드롬이 하나가 있다고 하자. 2번째 아이디어에서 앞/뒤를 검사한다는 의미를 조금 다르게 해석을 해볼거다. ABCBA를 이제부터 분해하기 시작할거다. 

팰린드롬!?

ABCBA안에 , 놀랍게도 BCB도 팰린드롬이다. 이게 왜 놀라운 사실이냐면, 일반화를 해보면 정말 놀라운 사실이란걸 알 수 있다.

길이가 Sn인 팰린드롬이 있을 때, Sn이 팰린드롬이라면,  S2로 시작해서, Sn-1로 끝나는 것도 팰린드롬이고, S3로 시작해서 Sn-2로 끝나는 것도 팰린드롬이고... 와 같이 재귀적인 구조로 팰린드롬은 사실 이루어져 있다는 사실을 알 수 있다.

 

재귀? DP를 어떻게 참아 ㅋㅋ 못참지!

 

DP

 

재귀적인 구조가 형성되면, 우리는 Dynamic Programming을 생각해줄 수 있다. DP Table을 정의해보자

정의 

• DP[S][E] = S부터 E까지 팰린드롬인지,아닌지 기록한 DP table

점화식

• DP[S][E] = True if word[s] == word[e] and DP[S+1][E-1] else False

이때, 반복하는 방식이 중요해지는데, 우리는 DP[S][E]일 때, DP[S+1][E-1]의 정보를 알고 있어야한다.

대각선으로 반복을 해야한다는 의미이다. 따라서, upper diagnal 방식으로 반복을 할거고 , DP table에 기록을 할거다.

이렇게 구현하면, S부터 E까지 팰린드롬 인지 아닌지 구분이 가능한 DP table이 완성이 된다!

import sys
input= sys.stdin.readline

def chk_Panlindrom():
    for idx in range(N):
        for start in range(N):
            end = start +idx
            if N<=end:
                break
            if idx==0:
                DP[start][end] = True
                continue
            if idx==1:
                if word[start] == word[end]:
                    DP[start][end] =True
                    continue
            if word[start] == word[end] and DP[start+1][end-1]:
                DP[start][end] = True
def Is_panlindrom(a,b):
    if DP[a-1][b-1]:
        return True
    else:
        return False

N=int(input().rstrip())
word =input().rstrip()
DP=[[False for _ in range(N)] for _ in range(N)]

a,b=map(int,input().split())
chk_Panlindrom()
for d in DP:
    print(d)
if Is_panlindrom(a,b):
    print(1)
else:
    print(0)