스택의 어원은 '쌓는다' 입니다. 어원에서 짐작할 수 있듯이, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 혹인 LIFO(Last IN First Out)이라고 합니다. 이 때, 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop 이라고 합니다.
📖 스택의 동작 원리 이해하기
빈 통(빈 스택)에 사탕을 넣는다고 하면, 아래와 같이 나타낼 수 있습니다.
📖 스택의 ADT
ADT는 우리말로 추상 자료형(abstract data type)인데요, 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요?
우선 스택에는 push, pop, isFull(가득찼는지 확인), isEmpty(비었는지 확인)과 같은 연산을 정의해야 합니다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top(맨 위=탑)도 있어야 합니다.
표와 그림으로 정리하면 아래와 같습니다.
| 구분 | 정의 | 설명 |
| 연산 | boolean isFull() | 스택에 들어 있는 데이터 개수가 maxSize 인지 확인해 boolean 값을 반환합니다. 가득 차 있다면, True, 아니면 False 입니다. |
| boolean isEmpty() | 스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환합니다. 데이터가 하나라도 있으면 False, 아니면 True 입니다. | |
| void push(ItemType item) | 스택에 데이터를 push합니다. | |
| ItemType pop() | 스택에서 최근에 push한 데이터를 pop하고, 그 데이터를 반환합니다. | |
| 상태 | Int top | 스택에서 최근에 push한 데이터의 위치를 기록합니다. |
| ItemType data[maxsize] | 스택의 데이터를 관리하는 배열입니다. 최대 maxsize개의 데이터를 관리합니다. |
그림은 스택의 ADT 를 나타낸 것입니다.
스택 외부와 내부에 노란색 네모로 표현한 연산과 상태가 보입니다. 그림에서는 연산 시 해야 할 동작과 상태가 가지고 있어야 할 값을 정의하고 있기는 하지만, 세부 내용 즉, 프로그래밍 언어는 무엇을 사용해야 하고 데이터는 이렇게 저장해야 한다는 등의 내용은 없습니다.
data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize-1 입니다. top은 가장 최근에 추가한 데이터의 위치를 참조합니다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1 이들어있습니다. top 초기값을 -1로 해주는 것이 국룰입니다.
그럼 ADT 만 알고 있으면 될까요? 코딩테스트에서는 문제에 적용할 자료구조 혹은 알고리즘을 파악하는 능력이 중요합니다. 문제에서 의도한 데이터 흐름이 스택에 딱 맞는지 알아차려야 하는 것이죠. 사실 어떠한 문제도 대놓고 "스택으로 푸세요" 하지 않습니다. 어떤 문제를 보고 "아~스택으로 푸는게 좋겠다"라는 생각이 들려면, ADT 에서 그치는 것이 아니라, 세부 구현 내용을 알면 좋습니다.
📖 스택 세부 동작에 대해 조금 더 자세히 알아보기
스택에 데이터를 추가하는 경우를 세부동작에 대해 생각해봅시다. → push(3)
스택에 데이터를 빼는 경우를 세부동작에 대해 생각해봅시다. → pop()
여기서 " 3 이 남았는데?" 라고 생각할 수 있습니다.
하지만, 앞서 정의한 스택의 ADT에서 top은 최근에 삽입한 데이터의 위치라고 했습니다. 즉, top 이 가리키는 위치가 -1 이 되면, 실제 data 배열에 데이터가 남아 있다고 하더라도 스택은 비어 있다고 인식합니다.
📖 스택 구현하기
코딩테스트에서 예를 들어, 데이터를 그냥 저장하고 순서와 상관 없이 임의 접근하기만 해도 되면, 배열을 사용하면 되지만, 최근에 삽입한 데이터를 대상으로 무언가를 연산해야 한다면, 스택을 떠올리는 것이 좋습니다. 이런 사고과정을 확립하기 위해, 스택 ADT를 구현해보겠습니다.
stack = [] # 스택 리스트 초기화
max_size = 10 # 스택의 최대 크기
def isFull(stack):
# 스택이 가득 찼는지 확인하는 함수
return len(stack) == max_size
def isEmpty(stack):
# 스택이 비어 있는지 확인하는 함수
return len(stack) == 0
def push(stack, item):
# 스택에 데이터를 추가하는 함수
if isFull(stack):
print("스택이 가득 찼습니다.")
else:
stack.append(item)
print("데이터가 추가되었습니다.")
def pop(stack):
# 스택에서 데이터를 꺼내는 함수
if isEmpty(stack):
print("스택이 비어 있습니다.")
return None
else:
return stack.pop()
그러나 파이썬의 리스트는 크기를 동적으로 관리하므로, max_size나 isFull() 함수, isEmpty() 함수는 실제 코딩 테스트 문제를 풀 때, 구현하지는 않습니다. max_size, isFull() 함수는 사용하지 않고, isEmpty() 함수는 len(stack)==0 으로 검사하곤 하죠.
그런데, push() 함수, pop() 함수를 구현한 부분을 보면, 실제 이 함수들이 하는 일은 리스트의 append() 메서드와 pop() 메서드를 호출하는 것이 전부입니다. 때문에, 추가, 삭제도 따로 구현하지 않고 append() 와 pop() 을 사용하면 되는 것이죠.
스택은 개념 자체는 어렵지 않으므로, 비교적 쉽게 이해할 수 있습니다. 하지만, 실전에 들어가서 문제를 풀다 보면 스택을 몰라서 풀지 못하는 것이 아닐, "이 문제는 스택을 활용해야 풀 수 있다" 라는 생각 자체를 못해서 풀지 못하는 경우가 더 많습니다. 방법은 결국 스택 관련 문제를 많이 풀어보면서 문제에 대한 감을 익히는 것이 중요합니다.
📖 몸풀기 문제
01. 괄호 짝 맞추기
[문제]
소괄호는 짝을 맞춘 열린 괄호 '('와 닫힌 괄호 ')'로 구성합니다. 문제에서는 열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열을 줍니다. 이 때, 소괄호가 정상으로 열고 닫혔는지 판별하는 solution() 함수를 구현하세요. 만약 소괄호가 정상적으로 열고 닫혔다면 True를, 그렇지 않다면 False를 반환하면 됩니다.
[제약조건]
- 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다.
- 상쇄 조건은 열린 괄호가 먼저 와야 하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 합니다.
- 더 상쇄할 괄호가 없을 때까지 상쇄를 반복합니다.
[입출력 예]
| 입력 | 출력 |
| (())() | True |
| ((())() | False |
[최종코드]
def solution(s):
stack = []
for i in s:
if i == "(":
stack.append(i)
elif len(stack) != 0 and stack[-1] == "(":
stack.pop()
else:
return False
# print(stack)
return len(stack) == 0
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution('(())()')) # 반환값 : True
print(solution('((())()')) # 반환값 : False
print(solution(')(')) # 반환값 : False
02. 10진수를 2진수로 변환하기
[문제]
10진수를 입력받아 2진수로 변환해 반환하는 solution 함수를 구현하세요.
[제약조건]
- 제약 조건 없음
[입출력 예]
| 입력 | 출력 |
| 10 | 1010 |
| 27 | 11011 |
| 12345 | 11000000111001 |
[최종코드]
# 푸는 방법은 다양하지만, stack 원리를 보여주기 위한 풀이
def solution1(n):
stack = []
while n > 0:
stack.append(str(n % 2))
n //= 2
return "".join(stack[::-1])
# 나머지를 이용한 풀이
def solution2(n):
s = ""
while n > 0 :
s += str(n % 2)
n //= 2
return s[::-1]
# bin 을 활용한 풀이
def solution3(n):
return bin(n)[2:]
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution1(12345)) # 반환값 : 11000000111001
# print(solution2(12345)) # 반환값 : 11000000111001
# print(solution3(12345)) # 반환값 : 11000000111001
03. 괄호 회전하기
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/76502
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[최종코드]
# deque 을 사용하지 않은 풀이 (회전을 인덱스로 구현한 풀이)
# 시간복잡도 : O(n^2)
def solution(s):
n = len(s)
answer = 0
pair = {']':'[','}':'{',')':'('}
for i in range(n):
stack = []
for j in range(n):
c = s[(i+j) % n] # 회전연산을 안하고 인덱스로 문자열 회전 구현
if c in "[{(":
stack.append(c)
else:
if not stack:
break
if stack[-1] == pair[c] :
stack.pop()
else:
break
else: # for문이 break 에 의해 끝나지 않고 끝까지 수행된 경우
if not stack:
answer += 1
return answer
# deque - rotate() 를 사용한 풀이
# 시간복잡도 : O(n^2)
from collections import deque
def correct(s):
stack = []
pair = {']':'[','}':'{',')':'('}
check = True
for i in s:
if i in '([{':
stack.append(i)
elif len(stack) != 0 and stack[-1] == pair[i]:
stack.pop()
else:
return False
return len(stack)==0
def solution(s):
s = deque(list(s))
answer = 0
for _ in range(len(s)):
s.rotate(-1)
if correct(s):
answer += 1
return answer
04. 짝지어 제거하기
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/12973
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[최종코드]
def solution(s):
stack = []
for a in s:
if len(stack) != 0 and stack[-1] == a:
stack.pop()
else:
stack.append(a)
return int(len(stack)==0)
💡 [추천문제]
05. 주식 가격
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/42584
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[최종코드]
# 시간초과 코드 - 그리디 -> 이렇게 풀면 안된다.
def solution(prices):
answer = []
for i in range(len(prices)):
tmp = 0
for j in range(i+1,len(prices)):
if prices[i] <= prices[j] :
tmp += 1
answer.append(tmp)
return answer
# 스택사용 - 효율적 코드
def solution(prices):
answer = [0] * len(prices)
stack = []
n = len(prices)
for idx,p in enumerate(prices):
while stack and p < prices[stack[-1]]:
j = stack.pop()
answer[j] = idx-j
stack.append(idx)
while stack:
j = stack.pop()
answer[j] = n-j-1
return answer
이 코드는 각 가격에 대해 스택을 사용하여 현재 가격보다 낮은 가격을 만나는 시점을 효율적으로 찾습니다.
스택에는 가격이 떨어지지 않은 시점의 인덱스를 저장합니다.
현재 가격이 스택의 마지막 가격보다 낮으면, 스택에서 최근 가격의 인덱스를 빼내고 해당 가격의 인덱스와의 차이를 계산합니다.
이 과정은 모든 가격에 대해 한 번씩 수행되므로 시간 복잡도는 O(n)입니다.
06. 크레인 인형 뽑기 게임
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/64061
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[최종코드]
def solution(board, moves):
n = len(board)
stack = []
answer = 0
for m in moves:
item = 0
for i in range(n):
if board[i][m-1] != 0:
item = board[i][m-1]
# print(item)
if len(stack) != 0 and stack[-1] == item:
stack.pop()
answer += 2
else:
stack.append(item)
board[i][m-1] = 0
break
# print(stack)
return answer07. 표 편집
[문제]
https://school.programmers.co.kr/learn/courses/30/lessons/81303
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[최종코드]
# solution 1
def solution(n, k, cmd):
# 각 행마다의 (위,아래) 가 저장되어 있는 page
page = {i:[i-1,i+1] for i in range(n)}
removed = []
for do in cmd:
if do == "Z": # 복구
up, position, down = removed.pop()
if up == -1: # 복구한 위치가 맨 첫행이라면,
page[down][0] = position # 그 위치의 down행의 up행이 복구한 위치
elif down == n: # 복구한 위치가 맨 끝행이라면,
page[up][1] = position # 그 위치의 up행의 down행이 복구한 위치
else:
page[up][1] = position # 복구한 위치의 up 행의 down이 복구한 위치
page[down][0] = position # 복구한 위치의 down 행의 up이 복구한 위치
elif do == "C": # 삭제
removed.append((page[k][0],k,page[k][1])) # removed에 (ip,현재위치,down) 저장
up, down = page[k]
if down == n: # 삭제되는 행이 맨 끝행이라면 현재 위치는 up 행
k = page[k][0]
else:
k = page[k][1] # 그 외에는 현재 위치는 down 행
if up == -1: # 삭제되는 행이 첫 행이라면,
page[down][0] = -1 # 현재 행의 down 행의 up이 -1
elif down == n: # 삭제되는 행이 맨 끝 행이라면,
page[up][1] = n # 현재 행의 up행의 down이 n
else:
page[up][1] = down # 현재 위치의 up 행의 down이 현재위치의 down
page[down][0] = up # 현재 위치의 down 행의 up이 현재위치의 up
else:
d, move = do.split(" ")
print(d)
if d == "U": # 위로 이동
for _ in range(int(move)):
k = page[k][0]
elif d == "D": # 아래로 이동
for _ in range(int(move)):
k = page[k][1]
answer = ["O"] * n
for r in removed:
answer[r[1]] = 'X' # 해당 position X 로 갱신
return "".join(answer)
# solution2
def solution(n, k, cmd):
up = [i-1 for i in range(n+2)]
down = [i+1 for i in range(n+1)]
k += 1 # 초기 위치
removed = []
for do in cmd:
if do == 'Z':
if removed:
recent = removed.pop()
down[up[recent]] = recent
up[down[recent]] = recent
elif do == 'C':
removed.append(k)
up[down[k]] = up[k]
down[up[k]] = down[k]
k = up[k] if n < down[k] else down[k]
else:
d,move = do.split(" ")
if d == 'D':
for _ in range(int(move)):
k = down[k]
elif d == 'U':
for _ in range(int(move)):
k = up[k]
answer = ["O"] * n
for i in removed:
answer[i-1] = "X"
return "".join(answer)
💡기초 추가문제
https://school.programmers.co.kr/learn/courses/30/lessons/12906
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/12909
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
https://school.programmers.co.kr/learn/courses/30/lessons/120853
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'컴퓨터 공부 > 🧮 알고리즘' 카테고리의 다른 글
| [코테] 코딩 테스트 합격자 되기 2주차 - 배열 (0) | 2024.01.12 |
|---|---|
| [코테] 코딩 테스트 합격자 되기 1주차 - 코딩 테스트 필수 문법 (4) | 2024.01.07 |
| [코테] 코딩 테스트 합격자 되기 1주차 - 알고리즘의 효율 분석 (0) | 2024.01.03 |
| 이진 탐색 - 탐색 범위를 반으로 좁혀가며 탐색하는 알고리즘 (0) | 2021.08.29 |
| 그래프 알고리즘 2 - 코딩 테스트에서 자주 등장하는 기타 그래프 이론 (0) | 2021.08.25 |