[Algorithm] 6. Stack

Author

고경수

Published

September 7, 2024

6. 스택

코딩 테스트 합격자 되기 - 파이썬 편 책 정리 내용입니다.

06-1 스택 개념

  • 스택(Stack)의 어원은 ‘쌓는다’ 이다.

  • 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조(Fisrt In Last Out)

  • 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop 이라고 한다.

- 시간 복잡도 분석하기

  • N은 dirs의 길이이다. dirs의 길이만큼 순회하므로 시간 복잡도는 O(N)이다.

06-2 스택의 정의

  • ADT: 추상 자료형(abstract data type), 인터페이스만 있고 실제로 구현은 되지 않은 자료형. 일종의 자료형의 설계도

스택의 ADT

- 정의해야 할 연산 및 변수

  1. 푸시(push)

  2. 팝(pop)

  3. 가득 찼는지 확인(isFull)

  4. 비었는지 확인(isEmpty)

  5. 탑(top)

스택 구현하기(python ver.)

  • 파이썬의 리스트는 크기를 동적으로 관리하므로 max_size나 isFull() 함수, isEmpty()함수는 실제 문제를 풀 때 구현하지 않는다.

    isEmpty()함수는 len(stack)==0 으로 검사

  • push() 함수, pop() 함수가 하는 일은 리스트의 append() 메서드, pop() 메서드와 동일 그러므로 다음과 같이 구현

stack = []

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop()
next_element = stack.pop()

# 스택의 크기를 구함
stack_size = len(stack)

# top_element : 3
# next_element : 2

06-3 몸풀기 문제

  • 가장 가까운(최근)이라는 키워드 보고 스택 떠올리기

06-4 합격자가 되는 모의 테스트

  • 회전관련한 문제는 실제로 회전을 시키면 연산량이 많으므로 모듈러와 인덱스를 사용하여 구현
n = len(s)
for i in range(n):
    stack = []
    for j in range(n):
        # 문자열을 회전시키면서 참조
        c = s[(i + j) % n]
        ...
  • 스택의 top 확인은 stack[-1] 을 이용

Summary

- 리마인드

  • 스택은 선입후출(FILO) 방식으로 데이터를 관리하는 자료구조

  • 파이썬의 리스트는 append(), pop() 메서드가 있다. 이를 사용하면 리스트를 스택처럼 사용할 수 있다.

  • 중간에 데이터를 삽입할 일이 많다면 배열은 비효율적이다. 다른 방법을 생각해야 한다.

- 추천문제

추가 질문(4주차)

질문

  1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요. 이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.
def solution(x):
    stack = []
    for char in x:
        stack.append(char)
    
    string = ''
    while stack:
        string += stack.pop()
    
    return string

solution('abcd')
'dcba'

  • 시간복잡도는 O(N), 공간복잡도는 문자열 길이만큼의 리스트 공간이 필요하므로 O(N)

  • 스택을 사용하지 않고 문자열을 뒤집는 방법은

    1. 슬라이싱을 사용
    string[::-1]
    1. 반복문을 사용
    reverse_s = ""
for char in s:
    reverse_s = char + reverse_s
    1. 재귀를 사용
    def reverse_string(s):
    if len(s) == 0:
        return s
    else:
        return reverse_string(s[1:]) + s[0]

    하는 방법 등이 있다.

  1. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요. 재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법을 예시를 통해 설명할 수 있나요?

  • 바로 위의 재귀를 사용한 방식을 보면, 다음과 같은 방식으로 스택이 동작한다.

    1. reverse_string("abcd") 호출 → 스택에 저장

    2. reverse_string("bcd") 호출 → 스택에 저장

    3. reverse_string("cd") 호출 → 스택에 저장

    4. reverse_string("d") 호출 → 스택에 저장

    5. reverse_string("") 호출 → 반환하고 스택에서 제거

    호출 스택에 쌓인 함수들이 끝에서 부터 차례로 반환되면서 문자열이 뒤집히게 된다.

  • 재귀 함수를 스택을 사용한 비재귀적 함수로 변환하기

    def reverse_string_iterative(s):
    stack = []
    result = ""

    # 문자열의 각 문자를 스택에 push
    for char in s:
        stack.append(char)

    # 스택에서 pop하여 결과에 추가
    while stack:
        result += stack.pop()

    return result

    1. 문자열의 각 문자를 스택에 추가

    2. 스택에서 문자를 하나씩 꺼내서 새로운 문자열에 추가

    이 방식은 재귀 함수가 호출 스택을 사용하듯, 직접 스택을 관리하여 문자열을 뒤집는다. 이를 통해 재귀 호출을 스택을 활용한 비재귀 방식으로 변환한 것

    이처럼 재귀 호출은 내부적으로 스택을 사용하기 때문에, 명시적인 스택 자료구조를 이용해 재귀적 알고리즘을 반복적인 방식으로 바꿀 수 있다.

코딩 문제

문제 1: HTML 태그 유효성 검사

HTML 문서에서 태그가 올바르게 열리고 닫혔는지 확인하는 프로그램을 작성하세요. 형태로 열리고 형태로 닫혀야 합니다. 태그 이름은 영문 소문자만 사용됩니다.

  • 입력: HTML 태그가 포함된 문자열이 주어집니다.

  • 출력: 태그가 올바르게 열리고 닫혔다면 True, 그렇지 않다면 False를 출력합니다.

예시 입력/출력

# 예시 입력 1
"<div><p>Hello</p></div>"

# 예시 출력 1
True

# 예시 입력 2
"<div><span>Hi</div></span>"

# 예시 출력 2
False

입출력 설명

  • 예시 1에서는 <div> 태그가 <p> 태그를 포함하고, 올바르게 닫히므로 True를 반환합니다.

  • 예시 2에서는 <span> 태그가 <div> 태그 내에서 닫히기 때문에 구조가 올바르지 않아 False를 반환합니다.

- 답안

def solution(string):
    stack = []
    record = False
    close = False

    for char in string:
        # "<" 일 때 record를 키고 다음부터 기록을 시작, ">" 일 때 record 를 끄고 저장된 값을 스택에 넣는다.
        # 그러나 "/" 가 나오면 그 값은 pop의 대상이다.
        
        if char == "/": # 닫는 태그
            close = True
            
        if char == ">": 
            record = False
            if close == True: # 닫는 태그일 때
                if stack[-1] != tmp[1:]: # [1:] 을 쓴 이유는 닫는 경우엔 "/"가 포함되어있기에
                    return False
                else:
                    stack.pop()
            else:
                stack.append(tmp) # 여는 태그일 때
        
        if record == True: # record가 켜져있으면 계속 한 문자씩 더한다.
            tmp += char
            
        if char == "<": # < 부터 record가 시작("<"는 포함되지 않음)
            record = True
            tmp = ""
            
    return True
solution("<div><p>Hello</p></div>")
True
solution("<div><span>Hi</div></span>")
False

문제 2: 역순 이진수 표현

주어진 양의 정수를 이진수로 변환한 후, 그 이진수를 뒤집어 정수로 다시 변환한 결과를 출력하는 프로그램을 작성하세요.

  • 입력: 하나의 양의 정수 N이 주어집니다.

  • 출력: 이진수를 뒤집어 변환한 결과 정수를 출력합니다.

예시 입력/출력

# 예시 입력 1
13

# 예시 출력 1
11

# 예시 입력 2
4

# 예시 출력 2
1

입출력 설명

  • 예시 1에서 13의 이진수 표현은 1101이고, 이를 뒤집으면 1011이 되어 10진수로 11입니다.

  • 예시 2에서 4의 이진수 표현은 100이고, 이를 뒤집으면 001이 되어 10진수로 1입니다.

- 문제 분석

  • 교재 09번 10진수를 2진수로 변환하기 내용을 응용해보자

  • 정확히 나온 결과 값을 다시 스택에 넣으면 거꾸로 뽑아낼 수 있을 것

    집어넣을 때마다 곱하는 값을 2배씩 해서 계속 곱해주기!

def solution(decimal):
    res = 0
    stack = []
    while decimal > 0:
        remainder = decimal % 2
        stack.append(str(remainder))
        decimal //= 2
    binary = ""
    while stack:
        binary += stack.pop()
        
    # binary가 완성됨.
    mul = 1
    for b in str(binary):
        stack.append(int(b)*mul)
        mul *= 2
        
    res = 0
    while stack:
        res += stack.pop()
    return res    
solution(13)
11
solution(4)
1