팰린드롬(Palindrome) [알고리즘 설명] & [파이썬 구현] 유찬맨

팰린드롬 알고리즘 설명 & 파이썬 구현

팰린드롬(Palindrome)은 앞으로 읽으나 뒤로 읽으나 같은 단어나 문장을 말합니다. 예를 들어 "level", "madam", "noon"과 같은 단어들은 팰린드롬이며, "hello", "world"는 팰린드롬이 아닙니다. 팰린드롬 알고리즘은 팰린드롬인지 아닌지를 판별하는 알고리즘입니다. 주로 문자열에 사용되지만, 숫자나 음성도 판별 할 수 있습니다.

 

---

 

팰린드롬 알고리즘을 파이썬으로 구현하는 가장 간단한 방법은 문자열을 처음부터 중간까지 검사하면서 각 문자가 서로 대칭인지 확인하는 것입니다. 아래와 같은 코드로 구현할 수 있습니다.

 

def is_palindrome(s: str) -> bool:
    for i in range(len(s) // 2):
        if s[i] != s[len(s) - i - 1]:
            return False
    return True

 

위 코드는 for문을 사용하여 각 문자를 검사하며, 문자열의 길이가 홀수라면 중간 문자는 검사하지 않아도 됩니다.

또한, python에서는 기본적으로 slicing 기능을 제공하므로, 아래와 같이 구현 가능 합니다.

 

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

s[::-1]으로 문자열을 reverse 할 수 있습니다. 그리고 그것을 s와 비교하여 판별 하면 됩니다.

---

팰린드롬 알고리즘은 문자열의 길이가 n 일 때, 그 문자열을 처음부터 n/2 까지 검사하며, 각 문자가 서로 대칭인지 확인하는 과정을 거칩니다. 이렇게 하면 문자열의 길이가 홀수인 경우에도 판별이 가능합니다.

시간복잡도는 O(n/2) 이므로 효율적인 알고리즘 입니다.