알고리즘의 공간 복잡도, 팰린드롬 문제로 초보자도 쉽게 이해하자

 

프로그래밍을 하다 보면 "공간 복잡도"라는 용어를 자주 접하게 됩니다.

공간 복잡도란 알고리즘이 실행되는 동안 얼마나 많은 메모리를 사용하는지를 나타내는 척도입니다.

이번 포스트에서는 팰린드롬(Palindrome) 문제를 통해 공간 복잡도가 무엇인지 초보자도 쉽게 이해할 수 있도록 설명해보겠습니다.

1. 팰린드롬이란?

팰린드롬은 앞에서 읽으나 뒤에서 읽으나 동일한 단어를 의미합니다.

예를 들어, "racecar", "level", "madam" 같은 단어들은 모두 팰린드롬입니다.

팰린드롬을 확인하는 문제는 흔히 인터뷰 문제나 알고리즘 학습에서 많이 등장하는데, 이 문제를 풀기 위한 방법들은 다양합니다.

각 방법마다 시간 복잡도뿐만 아니라 공간 복잡도도 다르다는 점이 중요한 포인트입니다.

1. 양 끝에서 비교하는 방법 (투 포인터 방식)

이 알고리즘은 문자열의 왼쪽 끝과 오른쪽 끝에서 시작해 하나씩 비교하면서 팰린드롬 여부를 확인합니다.

def is_palindrome(word):
    for left in range(len(word) // 2):
        right = len(word) - 1 - left
        if word[left] != word[right]:
            return False
    return True

공간 복잡도 분석

이 방식은 입력 문자열의 크기와 상관없이 고정된 양의 메모리만 사용하므로 O(1)의 공간 복잡도를 가집니다.

이 방법은 메모리 사용이 매우 적고 효율적입니다.

2. 문자열 뒤집기 방식

이 방법은 문자열을 뒤집은 후, 원래 문자열과 비교하는 방식입니다.

def is_palindrome(word):
    return word == word[::-1]

공간 복잡도 분석

이 방식은 문자열을 뒤집기 위해 새로운 문자열을 생성합니다.

따라서 입력 문자열의 길이 n에 비례하는 추가 메모리가 필요하므로, O(n)의 공간 복잡도를 가집니다.

3. 재귀 호출을 사용한 방법

팰린드롬을 확인하는 또 다른 방법으로 재귀 호출을 사용할 수 있습니다.

재귀적으로 문자열의 첫 번째 문자와 마지막 문자를 비교하면서, 비교가 끝나면 중간 부분으로 넘어가는 방식입니다.

def is_palindrome(word):
    if len(word) <= 1:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

공간 복잡도 분석

재귀 호출은 함수가 호출될 때마다 새로운 함수 호출 스택이 쌓이기 때문에, 함수가 호출되는 깊이만큼 추가 메모리가 필요합니다.

이 경우, 문자열의 길이 n에 비례하여 함수 호출이 이루어지므로, O(n)의 공간 복잡도를 가집니다.

4. 스택을 이용한 방법

스택 자료구조를 사용해 팰린드롬을 확인할 수도 있습니다.

문자열의 절반을 스택에 넣고, 나머지 절반을 꺼내면서 비교하는 방식입니다.

def is_palindrome(word):
    stack = []
    length = len(word)
    for i in range(length // 2):
        stack.append(word[i])
    
    start = (length // 2) + (length % 2)  # 짝수와 홀수에 따라 다르게 시작
    for i in range(start, length):
        if stack.pop() != word[i]:
            return False
    return True

공간 복잡도 분석

이 방법은 문자열의 절반을 스택에 저장해야 하므로, 스택에 최대 n/2개의 문자가 저장됩니다. 따라서 O(n)의 공간 복잡도를 가집니다.

4. 알고리즘별 공간 복잡도 비교

각 알고리즘의 공간 복잡도를 요약하면 다음과 같습니다:

1. 양 끝 비교 방법: O(1) - 추가 메모리 사용이 거의 없음.
2. 문자열 뒤집기 방법: O(n) - 새로운 문자열을 생성.
3. 재귀 호출 방법: O(n) - 함수 호출 스택 사용.
4. 스택 사용 방법: O(n) - 문자열 절반을 스택에 저장.

어떤 방법을 선택할까?

• 메모리 효율을 중시한다면, 양 끝 비교 방법(O(1))이 가장 적합합니다. 추가적인 메모리 사용이 거의 없기 때문입니다.
• 다만, 간단한 코드를 원한다면, 문자열 뒤집기 방법(O(n))이 직관적이고 코드가 간결해 활용하기 좋습니다.
• 재귀나 스택을 활용한 방법도 상황에 따라 유용할 수 있지만, 일반적으로 공간 복잡도가 더 크기 때문에 메모리 사용량이 신경 쓰이는 경우 주의가 필요합니다.

공간 복잡도 이해하기

공간 복잡도는 알고리즘을 설계할 때 고려해야 할 중요한 요소입니다.

팰린드롬 문제와 같은 간단한 문제도 다양한 방식으로 풀 수 있으며, 각 방법마다 메모리 사용량이 다릅니다.

알고리즘을 작성할 때는 공간 복잡도를 고려해 메모리 사용을 최적화하는 것이 중요합니다.

 

공감과 댓글은 저에게 큰 힘이 됩니다.

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱