알고리즘, 파이썬을 곁들인 (11) - Palindrome

오늘은 Palindrome(회문) 찾기 알고리즘을 알아보자.

바로 시작해보자.

---

먼저 Palindrome(회문)이 무엇인가.

회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.

즉, '기러기', '다시 합창합시다', '일요일', 'mom', 'wow'와 같이,
앞으로 읽어도 뒤로 읽어도 같은 단어나 문장 등등을 뜻한다고 한다.

그렇다면 Palindrome(회문) 찾기 알고리즘이란,
어떤 단어, 문장이 있을 때, 그 단어나 문장이 앞으로 읽어도 뒤로 읽어도 동일한가.
를 알아내는 알고리즘이 되겠다.

 

 

 

흠. 본능적으로 생각난 알고리즘을 작성해보자.

1. 단어의 길이를 가져온다.
2. 0부터 단어의 길이를 2로 나눈 몫까지 순회한다.
   순회하는 인덱스 번호는 n으로 표현하였다.
   
   1. (단어의 길이 - 1) - n 의 값을 구한다.
   2. 단어의 n번째와 ((단어의 길이 - 1) - n)번째의 문자가 같은 지 비교한다.
      1. 다르다면, 회문이 아닌 단어이므로 순회를 종료한다.
3. 순회 도중에 순회가 종료하지 않았다면, 그 단어는 회문이다.

 

 

 

바로 구현해 보자.

word = '다시합창합시다'

word_len = len(word)
for n in range(word_len // 2):
    if word[n] != word[word_len - 1 - n]:
        print('회문이 아닙니다.')
        break
else:
    print('회문입니다.')

출력 결과 : 

회문입니다.

잘 작동했다. 

 

 

 

다음으로는 파이썬의 내장 기능을 사용해서 알고리즘을 짜보았다.

1. 단어(문자의 리스트)를 거꾸로 배치한다.
2. 단어와 거꾸로 배치한 단어를 set에 넣는다.
3. set의 길이를 확인한다.
   1. 길이가 1이면, 회문이다.
   2. 길이가 2면, 회문이 아니다.

 

 

 

바로 구현해 보자.

word = '다시합창합시다'

print('회문입니다.' if len({word, word[::-1]}) == 1 else '회문이 아닙니다.')

출력 결과 : 

회문입니다.

잘 작동했다.

 

 

 

마지막으로 파이썬의 메모리 저장과 값 참조 방식을 통해,
알아내는 방법으로 알고리즘을 짜보았다.

+ 같은 값이라면 메모리에 한 번만 저장하고 이 메모리 주소를 공유한다.
라는 것에 모티브를 받아 작성해보았다.

+ 단어의 길이가 너무 길면 이 경우에는 정상 작동하지 않는다.
실제로 파이썬은 '2 ** 65' 부터는 각각의 '2 ** 65'마다 다른 메모리 주소를 참조한다.
이는 길거나, 큰 숫자를 메모리에 저장하는 파이썬의 방식 때문이지 않을까 추측해본다.

1. 단어가 저장된 메모리 주소 값을 가져온다.
2. 단어(문자의 리스트)를 거꾸로 배치한다.
3. 거꾸로 배치한 단어가 저장된 메모리 주소 값을 가져온다.
4. 단어가 저장된 메모리 주소 값과 거꾸로 배치한 단어가 저장된 메모리 주소 값을 비교한다.
   1. 메모리 주소 값이 같다면, 회문이다.
   2. 메모리 주소 값이 다르다면, 회문이 아니다.

 

 

 

바로 작성해 보자.

word = '다시합창합시다'

print('회문입니다.' if id(word[:(len(word)//2)]) == id(word[::-1][:len(word)//2]) else '회문이 아닙니다.')

출력 결과 : 

회문입니다.

잘 작동했다.

 

실험 결과, 70,000,000자리의 문자열은 회문이라고 판단하나,
700,000,000자리의 문자열은 회문이라고 판단하지 못한다.

import sys

word1 = '다시합창합시다' * 10000000
word2 = '다시합창합시다' * 100000000

print('word1 info:', sys.getsizeof(word1), len(word1))
print('word2 info:', sys.getsizeof(word2), len(word2))

print('회문입니다.' if id(word1[:(len(word1)//2)]) == id(word1[::-1][:len(word1)//2]) else '회문이 아닙니다.')
print('회문입니다.' if id(word2[:(len(word2)//2)]) == id(word2[::-1][:len(word2)//2]) else '회문이 아닙니다.')

출력 결과 :

word1 info: 140000074 70000000
word2 info: 1400000074 700000000
회문입니다.
회문이 아닙니다.

코드에 2로 나눈 몫으로 구했으니,
아마 35,000,000 ~ 350,000,000의 중간 어딘가에서 부터 메모리에 저장되는 방식이 바뀌는 듯하다.