[파이썬] 문자열 알고리즘의 응용과 효율적인 구현
소개
문자열은 프로그래밍에서 중요한 역할을 합니다. 문자열을 다루는 알고리즘은 문서 처리, 언어 분석, 암호화 등 여러 응용 분야에서 필수적입니다. 이 블로그 포스트에서는 문자열 알고리즘의 다양한 응용과 효율적인 구현에 대해 알아보겠습니다.
1. 반복 문자열 찾기
주어진 문자열에서 가장 긴 반복 문자열을 찾는 알고리즘은 다양한 응용 분야에서 사용됩니다. 이 알고리즘은 하나의 문자열을 반복으로 이어붙인 문자열을 만들고, 부분 문자열 중 가장 긴 길이를 가지는 것을 찾아내는 방식으로 동작합니다.
def find_longest_repeated_substring(s):
n = len(s)
max_len = 0
max_idx = 0
for i in range(n):
for j in range(i+1, n):
k = 0
while j+k < n and s[i+k] == s[j+k]:
k += 1
if k > max_len: # 더 긴 반복 문자열을 찾은 경우
max_len = k
max_idx = i
return s[max_idx:max_idx+max_len]
s = "abcabcaabc"
result = find_longest_repeated_substring(s)
print(result) # 'abca'
2. 팰린드롬 여부 확인
문자열이 팰린드롬인지 확인하는 알고리즘은 회문, 회전 대칭, 암호화 등 다양한 분야에서 사용됩니다. 이 알고리즘은 문자열을 앞에서부터 읽을 때와 뒤에서부터 읽을 때 동일한지를 판별하여 팰린드롬 여부를 확인합니다.
def is_palindrome(s):
n = len(s)
for i in range(n//2):
if s[i] != s[n-i-1]: # 양 끝의 문자가 다른 경우
return False
return True
s = "level"
result = is_palindrome(s)
print(result) # True
3. 문자열 압축
문자열을 압축하여 저장하는 알고리즘은 데이터 압축, 파일 압축 등에서 사용됩니다. 이 알고리즘은 연속되는 인접한 문자를 하나의 숫자로 표현하여 문자열을 압축합니다.
def compress_string(s):
n = len(s)
compressed = ""
count = 1
for i in range(1, n):
if s[i] == s[i-1]: # 이전 문자와 동일한 경우
count += 1
else: # 이전 문자와 다른 경우
compressed += s[i-1] + str(count)
count = 1
compressed += s[n-1] + str(count) # 마지막 문자 처리
return compressed
s = "aaabbbccc"
result = compress_string(s)
print(result) # 'a3b3c3'
마무리
이 블로그 포스트에서는 문자열 알고리즘의 응용과 효율적인 구현에 대해 알아보았습니다. 반복 문자열 찾기, 팰린드롬 여부 확인, 문자열 압축 등 다양한 응용 사례를 다루었습니다. 이러한 문자열 알고리즘을 효율적으로 구현하여 다양한 프로그래밍 문제를 해결해보세요!