스택을 사용하여 문제를 해결하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 스택을 사용하여 해결될 가능성이 높습니다.

후입선출 특성 (Last In, First Out, LIFO)

스택은 후입선출 방식으로 동작합니다. 즉, 나중에 삽입된 요소가 먼저 제거됩니다. 따라서, 후입선출 특성을 이용해야 하는 문제에서 스택이 효과적입니다.

재귀적 구조 (Recursive Structure)

재귀적으로 정의된 문제를 반복문을 사용하여 해결할 때 스택이 유용합니다. 함수 호출의 재귀적인 구조를 명시적으로 스택을 사용하여 구현할 수 있습니다.

스택으로 접근하는 게 효율적인 경우

스택의 대표적인 예시는 괄호의 유효성을 검사하는 문제입니다.

괄호의 유효성을 검사하는 과정은 아래와 같습니다. 예를 들어, 문자열 "(([]))"이 주어졌을 때, 괄호가 유효한지 검사합니다.

이를 코드로 구현하면 아래와 같습니다.

python코드 복사def is_valid_parentheses(s):
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}
    
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    
    return not stack

위의 코드에서 스택은 열린 괄호를 저장하고, 닫힌 괄호를 만날 때마다 스택의 최상단 요소와 비교합니다. 이 방법은 후입선출 특성을 이용하여 괄호의 짝을 맞추므로 효율적입니다.

스택으로 접근하는 게 효율적이지 않은 경우

반대로, 스택이 비효율적인 경우도 있습니다. 대표적인 예로는 배열의 합을 계산하는 문제가 있습니다.

배열의 합을 계산하는 과정은 아래와 같습니다.

• 주어진 배열의 모든 요소를 더합니다.

이를 코드로 구현하면 아래와 같습니다.

python코드 복사def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

이 코드에서, 스택을 사용하여 각 요소를 저장하고 꺼내어 더할 수도 있습니다. 그러나 이는 불필요한 메모리 사용과 연산을 증가시킵니다. 단순히 반복문을 사용하여 배열의 합을 구하는 것이 더 효율적입니다.

python코드 복사def sum_array_with_stack(arr):
    stack = []
    for num in arr:
        stack.append(num)
    
    total = 0
    while stack:
        total += stack.pop()
    
    return total

이와 같이, 배열의 합을 계산하는 문제는 스택을 사용하지 않는 것이 더 효율적입니다. 스택의 후입선출 특성이 불필요하게 사용되기 때문입니다.

따라서, 스택을 사용해야 하는 문제는 주로 후입선출 특성을 활용해야 하는 문제나 재귀적인 구조를 반복문으로 해결해야 하는 문제입니다.