[코딩테스트] No.4 스택-6장

6-1. 스택 개념

 

스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 

먼저 들어간 것이 마지막에 나오는 규칙을 선입후출, FILO(First In Last Out)이라고 한다. 

이때, 스택에 삽입하는 연산을 push, 빼는 연산을 pop이라고 한다. 

 

6-1. 스택의 정의

 

스택 자료형의 동작 형태를 설계하는 것은 추상 자료형(ADT)을 정의하는 것이다. 

추상 자료형ADT(abstract data type) 이란?

=> 인터페이스만 있고 실제 구현은 되지 않은 자료형

 

스택은 push, pop, 스택이 가득 찼는지 확인(isFull), 스택이 비었는지 확인isEmpty)과 같은 연산을 정의해야 한다. 

또한 스택에는 최근에 삽입한 데이터의 위치(현재 가리키는 인덱스)를 저장할 함수인 top도 있어야 한다. 

 

스택 구현하기

 

스택은 최근에 삽입한 데이터를 대상으로 뭔가 연산 해야 할 경우 적합. 

 

# 스택 ADT 구현

stack = [] #스택 리스트 초기화 
max_size = 10 # tmxordml 최대 크기 

def ifFull(stack):
    # 스택이 가득 찼는지 확인하는 함수 
    return len(stack) == max_size

def isEmpty(stack):
    # 스택이 비어있는지 확인하는 함수 
    return len(stack) == 0

def push(stack, item):
    # 스택에 데이터를 추가하는 함수
    if ifFull(stack):
        print("스택이 가득 찼다.") 
    else:
        stack.append(item)
        stack.append("데이터가 추가됐다. ")

def pop(stack):
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack):
        print("스택이 비었다. ")
        return None
    else:
        return stack.pop()

 

그러나 파이썬의 리스트는 크기를 동적으로 관리하기 때문에 max_size나 isFull(), isEmpty()함수는 따로 구현하지 않는다. 

코드의 push(), pop()함수는 기존의 원소 추가 함수append(), 원소 꺼내는 함수 pop()이 있기 때문에 따로 구현하지 않아도 된다. 

 

 

주의: 실전에서는 문제에 스택을 활용해야 풀 수 있다는 생각을 하지 못해서 문제를 풀지못하는 경우가 대부분임

따라서 스택 관련 문제를 많이 풀어보고, 해당 문제는 스택을 사용하면 좋겠다는 감을 익히는 것이 중요함

 

---

 

질문

1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요. 이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.

답:

 

<스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계>

 

문자열의 길이가 n이라고 가정한다. 

1. 문자열의 문자를 임의의 리스트에 하나씩 넣는다. 

2. 빈 임의의 문자열 변수를 하나 선언한다. 

3. 임의의 리스트에서 pop()을 하여 꺼낸 값을 빈 임의의 문자열 변수에 + 연산을 하여 추가한다. 

3번은 문자열의 길이만큼 행한다. 

 

<위 알고리즘의 시간 및 공간 복잡도>

 

전체 시간복잡도 = 1번 과정에 대한 시간 복잡도 n + 3번 과정에 대한 시간복잡도 n^2 = O(n^2)

전체 공간 복잡도 = 문자열의 길이 n만큼 nbyte = O(n)

 

<스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법>

 

파이썬의 슬라이스를 사용해 뒤집는 방법이 있다. 

 

 

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

 

답:

 

<스택이 재귀적인 함수 호출과 어떻게 관련이 있는가?>

 

재귀적인 함수 호출은 함수 호출 조건을 5로 준다면, 첫번째로 함수를 호출 한것이 해당 함수를 두번째로 호출하게되고 두번째로 호출 한 함수에서 해당 함수를 세번째로 호출하게 되고 , , ,이런식으로 진행이 되다가 조건에 따라 추가적인 함수 호출을 하지않게 된다. 마지막으로 함수를 호출한 것이 실행되면서 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 네번째로 호출한 함수에서 다섯번째로 함수 호출한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 세번째로 호출한 함수에서 네번째로 함수 호출을 한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다... 이렇게 첫번째 함수까지 처리되어 재귀 함수의 실행이 끝난다. 

 

이렇듯 재귀적인 함수의 호출은 스택의 LIFO(Last In, First Out) 원칙에 따라 진행되는 것을 알 수 있다. 

 

<재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법과 그 예시>

 

비재귀적 방식이란 함수가 자기 자신을 호출하지 않고, 대신 반복문과 같은 구조를 사용해서 문제를 해결하는 방식이다. 

예를들면 대상인 피보나치 함수를 재귀로 구현하면 다음과 같다. 

 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
print(fibonacci(3))

 

위 재귀 함수를 비재귀적 방식으로 다시 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    
    return b

print(fibonacci(3))

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)