스택??
- 스택(Stack) 자료구조는 입력으로 들어온 순서대로 데이터를 스택의 가장 밑 부분인 하단에 차곡차곡 쌓는다.
- 데이터를 출력할 때는 맨 마지막으로 입력된 스택의 상단 부분의 데이터를 출력한다.
- 즉, 나중에 입력된 데이터가 가장 먼저 출력되는 구조이다.
- 1, 2, 3 순서대로 스택에 삽입할 시 1 위에 2, 2 위에 3이 올려져 있다.
- 출력할 때는, 맨 마지막에 입력되었던 3이 출력되고, 그 후 2, 1 순서대로 출력된다.
- 실생활에서의 예를 들어보면
- 스택은 방금 닦은 접시를 항상 접시 더미 맨 위에 올려놓게 되고, 접시가 필요할 때마다 맨 위에 있는 접시를 꺼내게 되는 상황과 같을 때 쓰일 수 있다.
- 한 번의 입력 시 O(1)의 시간이 걸리며 한 번의 출력 시 O(1)의 시간이 걸리므로 n개의 데이터를 스택에 넣으면 O(n), n개의 데이터를 스택에서 빼내면 O(n)이 걸리는 시간복잡도가 있다.
스택의 잘못된 사용 예와 잘 사용된 예
- 스택의 개념을 확실히 이해해서 어떨 때 스택을 쓰는지 알고, 요구하는 문제가 스택을 사용하여 풀 수 있다는 확신이 들 때 스택을 사용하여야 한다.
- 한 예로 회사의 회게팀으로서, 부서별로 회식 장부를 관리하는 프로그램을 만들었다고 해보자.
- A 부서가 200,000원어치의 회식을 하여 스택에 정보를 추가한다.
A 부서 : 200,000
...
총비용 = 200,000- B 부서가 900,000원어치의 회식을 하여 스택에 정보를 추가한다.
B 부서 : 900,000
A 부서 : 200,000
...
총비용 = 1,100,000- 이때, 최근 부서(B 부서)가 600,000원을 900,000원으로 잘못 말했다고 한다. 그렇다면 스택의 가장 위의 정보를 변경하면 된다.
B 부서 : 600,000
A 부서 : 200,000
...
총비용 = 800,000- 위 예에서는 입력 부서가 슽개의 최상단 부서였으므로 스택을 사용하여 해결할 수 있었지만, 최근 부서가 아닌 A 부서가 값을 잘못 말했다면 스택의 최상단값뿐만 아니라 스택 내부를 확인해야 하므로 스택의 사용 의미를 잃어버린다.
- 즉 이러한 회계 장부 프로그램을 스택으로 구현한 것은 잘못된 선택이 되는 것이다.
1. 컴퓨터가 프로그래밍 코드를 해석하는 방법
- 프로그래밍 코드를 컴퓨터가 실행하는 방법은 위에서부터 아래로 한 줄씩 해석하며 실행한다.
- 이때 함수의 호출 부분이 있다면 스택 영역에 함수를 쌓아둔 후 스택 영역의 최상단 함수를 따라 코드를 실행한 후 완료 시 최상단 함수를 지운다.
def first():
print(1)
second()
print(-1)
def second():
print(2)
third()
print(-2)
def third():
print(3)
print('start')
first()
print('end')- 위 코드를 컴퓨터가 실행하기 위해서
- 코드라인 1~4는 first라는 이름의 함수를 만들어둔 것으로 해석하고
- 코드라인 6~9는 second라는 이름의 함수를 만들어둔 것으로 해석하고
- 코드라인 11~12는 third라는 이름의 함수를 만들어둔 것으로 해석한다.
그 후에
- 코드라인 14의 print('start') 를 통해 'start'가 출력되고
- 코드라인 15의 first 함수를 호출했으므로 스택 영역에는 first 함수를 추가한 후 코드라인 1~4를 실행한다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| first 함수 | start |
- 코드라인 2를 통해 '1'이 출력된다.
- 코드라인 3에서 second 함수를 호출했으므로 스택 영역에는 second 함수를 추가한 후 코드라인 4가 아닌 코드라인 6~9로 이동한다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| second 함수 | start |
| first 함수 | 1 |
- 코드라인 7을 통해 '2'가 출력된다.
- 코드라인 8에서 third 함수를 호출했으므로 스택 영역에는 third 함수를 추가한 후 코드라인 9가 아닌 코드라인 11~12로 이동한다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| third 함수 | start |
| second 함수 | 1 |
| first 함수 | 2 |
- 코드라인 12를 통해 '3'을 출력한 후 third 함수가 종료되었으므로 스택 영역 최상단 함수를 지운다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| second 함수 | start |
| first 함수 | 1 |
| 2 | |
| 3 |
그 다음 이동할 코드라인은 9로,
- 코드라인 8에서 third 함수를 실행한 후부터 시작한다.
- 코드라인 9를 통해 '-2'를 출력한 후 second 함수가 종료되었으므로 스택 영역 최상단 함수를 지운다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| first 함수 | start |
| 1 | |
| 2 | |
| 3 | |
| -2 |
그 다음 이동할 코드라인은 4로,
- 코드라인 3에서 second 함수를 실행한 후부터 시작한다.
- 코드라인 4를 통해 '-1'을 출력한 후 first 함수가 종료되었으므로 스택 영역 최상단 함수를 지운다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| (비어 있음) | start |
| 1 | |
| 2 | |
| 3 | |
| -2 | |
| -1 |
마지막으로 코드라인 15에서 함수 호출이 끝났다.
- 코드라인 16의 print('end')을 통해 end를 출력한다.
| 스택 영역 상태 | 현재 출력 결과 |
|---|---|
| (비어 있음) | start |
| 1 | |
| 2 | |
| 3 | |
| -2 | |
| -1 | |
| end |
- 스택 자료구조는 데이터들의 입력이 들어올 때 스택 최상단과의 조화가 이루어지며, 빠른 시간복잡도 O(n)으로 작업을 진행하기 위해 쓰는 자료구조
스택을 포함한 다양한 자료구조의 올바른 사용
- 스택은 자료구조이므로 스택 자체는 코드로 구현되어 있다.
class Node:
def __init__(self, data):
self.data = data
self.next = next
class Stack:
def __init__(self):
self.head = None
def is_empty(self):
if not self.head:
return True
return False
def push(self, data):
add_node = Node(data)
add_node.next = self.head
self.head = add_node
def pop(self):
if self.is_empty():
return None
ret_data = self.head.data
self.head = self.head.next
return ret_data
def peek(self):
if self.is_empty():
return None
return self.head.data- 하지만 이를 구현하는 것은 어렵고, 프로그램 문제를 풀기 위해 스택을 쓸 때마다 스택 자체를 구현하는 것도 매우 비효율적이므로 실제 문제를 풀 때는 각 프로그램 언어에 내장되어있는 스택을 사용하면 쉽게 사용할 수 있다.
- 파이썬의 경우 ArrayList에서 사용했던 리스트를 통해 스택을 사용할 수 있다.
arr = []- 크게 스택을 통해 사용하는 기능은 5가지 이다.
① push : 데이터를 스택에 추가한다(스택의 하단부터 상단으로 차곡차곡 쌓는다).
② pop : 스택의 최상단 데이터를 삭제한다.
③ top : 스택의 최상단 데이터가 무엇인지 확인한다.
④ size : 스택에 데이터가 몇 개 들어있는지 확인한다.
⑤ empty : 스택이 비어 있는지 확인한다(데이터가 없는지 확인).
스택을 사용하는 예제 1 - 스택
[문제]
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.- push X : 정수 X를 스택에 넣는 연산이다. - pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. - size : 스택에 들어있는 정수의 개수를 출력한다. - empty : 스택이 비어있으면 1, 아니면 0 을 출력한다. - top : 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.[입력]
첫째 줄에 주어지는 명령의 수 N(1 <= N <= 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.[출력]
출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1 예제 출력 1 예제 입력 2 예제 출력 2 14 2 7 -1 push 1 2 pop -1 push 2 0 top 123 top 2 push 123 123 size 1 top -1 empty -1 pop -1 pop 0 top pop 1 pop pop -1 size 0 empty 3 pop push 3 empty top
해답코드
import sys
n = int(sys.stdin.readline())
stack = [] # stack을 사용하기 위한 변수를 생성한다(파이선에서 스택은 리스트 [] 를 이용하여 사용할 수 있다.
for i in range(n):
command = sys.stdin.readline().split() # 해당 명령어를 한 줄씩 입력받는다.
if command[0] == 'push': # 명령어가 push라면 스택에 숫자를 넣는다(append() 함수를 사용한다).
stack.append(command[1])
elif command[0] == 'pop': # 명령어가 pop 이라면
if len(stack) == 0: # 스택의 크기가 0이라면 -1을 출력한다.
print(-1)
else: # 스택의 크기가 0이 아니라면 스택의 최상단을 출력 한 후 삭제한다.
print(stack.pop())
elif command[0] == 'size': # 명령어가 size라면 스택의 크기를 출력한다.
print(len(stack))
elif command[0] == 'empty': # 명령어가 empty라면
if len(stack) == 0: # 스택의 크기가 0이라면 1을 출력한다.
print(1)
else: # 스택의 크기가 0이 아니라면 0을 출력한다.
print(0)
elif command[0] == 'top': # 명령어가 top이라면
if len(stack) == 0: # 스택의 크기가 0이라면 -1을 출력한다.
print(-1)
else: # 스택의 크기가 0이 아니라면 스택의 최상단을 출력한다.
print(stack[-1])- 스택 사용에 있어서 주의할 점은 잘못된 배열 인덱스에 접근하여 오류가 날 수 있으므로 스택의 최상단이 비어있는지 확인하고 써주어야 한다.
스택을 사용하는 예제 2 - 쇠막대기
[문제]
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠박대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. : 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되 끝점은 겹치지 않도록 놓는다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. - 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저의 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍'()'으로 표현된다. 또한 모든'()'는 반드시 레이저를 표현한다. 2. 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
[입력]
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.[출력]
잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.
예제 입력 1 예제 출력 1 ( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) ) 17
예제 입력 2 예제 출력 ( ( ( ( ) ( ( ) ( ) ) ) ( ( ) ) ( ) ) ) ( ( ) ( ) ) 24
문제설명
- 문제를 좀 더 자세히 분석해보면,
붙어있는 괄호 '()' : 레이저를 발사하여 현재 위치에서 쇠막대기를 자른다.
붙어있지 않는 괄호 '(' : 쇠막대기가 새로 생성되는 위치이다.
붙어있지 않는 괄호 ')' : 쇠막대기가 종료되는 위치이다.- ( ( ( ( ) ( ) ) ) ) 를 예시로 본다면
'(((' 쇠막대기가 3개 생성된 후
'()' 레이저를 발사하면 쇠막대기의 총 개수는 3이 추가되고,
'() 레이저를 발사하면 쇠막대기의 총 개수는 3이 추가되고,
')' 쇠막대기가 종료될 때 총 개수는 1이 추가된다.
')' 쇠막대기가 종료될 때 총 개수는 1이 추가된다.
')' 쇠막대기가 종료될 때 총 개수는 1이 추가된다.- 기본 규칙은,
1. '('를 만날 때마다 스택에 '('를 추가한다(쇠막대기의 개수를 추가하기 위해).
2. 스택의 최상단이 '('이고, ')'를 만난다면 스택의 크기만큼 총 개수에 추가한다(레이저를 발사하면 현재 쇠막대기의
개수만큼 총 개수가 증가하기 때문이다).
3. ')'를 만난다면 총 개수에 1을 추가한다(쇠막대기가 종료되면 총 개수는 1이 증가하기 때문이다).- 자료구조를 이해하고 생각해봤을때,
1. 레이저를 발사하면 현재 어딘가에 쌓인 쇠막대기만큼 총 개수가 증가하고
2. 어딘가에 쌓는 시점은 '('를 만났을 때이며
3. 어딘가에 쌓은 것을 없애는 시점은 ')'를 만났을 때다.해답코드
galho = input()
stack = []
answer = 0
for i in range(len(galho)):
if galho[i] == '(': # '('를 만날 때마다 스택에 '('를 추가한다.
stack.append(galho[i])
else:
if galho[i-1] == '(': # 스택의 최상단이 '('이고, ')'를 만난다면 스택의 크기만큼 총 개수에 추가한다.
stack.pop()
answer += len(stack)
else: # ')'를 만난다면 총 개수에 1을 추가한다.
stack.pop()
answer += 1
print(answer)스택을 사용하는 예제 3 - 크게 만들기
[문제]
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N과 K가 주어진다. (1 <= K <= N <= 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.
[출력]
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
예제 입력 1 예제 출력 1 4 2 94 1924
예제 입력 2 예제 출력 2 7 3 3234 1231234
예제 입력 3 예제 출력 3 10 4 775841 4177252841
문제 설명
- 무슨 숫자를 지우든 결국에 숫자 k개를 지우는 것은 똑같으므로 맨 앞의 수가 가장 클수록 정답인 가장 큰 수를 얻을 수 있게 된다.
- 이를 위해 현재 인덱스 위치값보다 현재 인덱스 -1 위치값이 작고 지울 수 있는 횟수 k 가 남아있다면 현재 인덱스 -1 위치값을 지워주면 된다.
- 위의 설명을 코드화하면
for num in number:
if answer[-1] > ni,"
del answer[-1]해답 코드
n, k = map(int, input().split()) # n, k 그리고 n개의 수를 입력받는다.
number = list(input())
answer = [] # 스택으로 이용할 answer 변수를 생성한다.
cnt = k
for num in number: # for문을 통해 number 배열을 순회한다.
# answer 스택이 비어있지 않고 지울 수 있는 횟수 k가 남아있고, answer의 마지막 값이 num보다 작다면
# answer의 마지막 값을 지운다.
while answer and cnt > 0 and answer[-1] < num:
del answer[-1]
cnt -= 1
answer.append(num) # 그 후 현재 순회 중인 값 num을 answer에 추가한다.
print(''.join(answer[:n-k])) # 정답을 출력한다.
데이터 사이언스 입문