코딩 테스트 완전 정복 ・ 스택

 

스택의 ADT라는 것을 정의해보고 실제 스택이 동작하는 원리를 설명해보겠습니다.

ADT는 abstract data type (추상 자료형)입니다. 

추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형 입니다.

 

언어에 따라 표준 라이브러리에서 스택 제공 여부는 다릅니다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 append() 메서드, push() 메서드로 스택을 대체할 수 있습니다. deque은 한쪽으로만 데이터 삽입, 삭제 할 수 있는 스택과는 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조 입니다.

 

스택의 ADT(연산과 상태)

스택 세부 동작에 대해 자세히 알아보기 

스택에 데이터를 추가하는 경우를 생각해봅시다. 푸시 연산을 수행할 때  스택 내부에서 일어나는 과정입니다. 그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여줍니다. 연산 과정은 push(3)을 호출하면 내부적으로 1. Isfull()을 수행해 우선 data 배열에 데이터가 가득 찼는지 확인하고, 2. 그렇지 않다면 top을 1만큼 증가시킨 후 top이 가리키는 위치 3. data[0]에 3을 추가합니다.

 

pop() 함수의 경우 내부족으로 1. isEmpty() 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인하고, 데이터가 있다면 2. top을 1만큼 감소시키고 3. 데이터 '3'을 반환합니다. 여기서 '3이 남아있는데?'라고 생각할 수도 있습니다. 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했습니다. 즉, top이 가리키는 위치는 -1이므로 실제 data 배열에 데이터가 남아있더라도 스택은 비어있다고 보아도 됩니다.

 

스택 구현하기

코딩 테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요합니다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차리는 것이 중요하죠. 예를 들어 데이터를 그냥 저장하고 순서와 상관없이 임의 접근하기만 해도 된다면 배열을 사용하면 되지만, 최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋습니다. 

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

 

 

 

10진수를 2진수로 변환하기

def solution(decimal):
  stack = [ ]
  while decimal > 0:
    remainder = decimal % 2
    stack.append(str(remainder))
    decimal //= 2
  binary = ""
  while stack:
    binary += stack.pop( ) 
# 이 문제에서는 스택 활용을 보여주기 위해 pop()을 했지만 문자열에 계속해서 문자를 더할 때는 join() 메서드가 더 효율적입니다.
  return binary