stack (1)

Stack은 LIFO (List In, First Out) 자료구조입니다.

가장 최근에 삽입된 데이터가 가장 먼저 제거됩니다.

 

python에서 Stack은 주로 List로 구현됩니다.

 

 

 

python에서 Queue은 주로 Deque로 구현됩니다.

Deque는 양 끝에서 O(1) 시간복잡도의 자료구조입니다.

 

 

 

 

✘ python List 특성

• Dynamic array: 메모리 관리 측면에서 효율적
• Over allocation: 리스트 크기를 초과하여 여유 메모리 할당
  python list는 새로운 요소가 추가될 때마다 매번 메모리 할당 X
• Reference counting: 참조 카운팅 방식으로 메모리 관리
  Garbage collector로 참조 카운트가 0이 된 객체를 자동 메모리 해제

+ deque는 이중 연결 리스트로 구현되어, 양쪽 끝에서 추가, 삭제가 효율적

 

✘ python List Copy

• 얕은 복사 (Shallow Copy)
  • 리스트의 참조(reference)만 복사
  • 한 리스트를 변경 시키면 다른 리스트에도 영향

original = [1, 2, 3]
copy_list = original[:]  # 슬라이싱을 사용한 복사

original = [1, 2, 3]
copy_list = list(original)  # list() 함수를 사용한 복사

original = [1, 2, 3]
copy_list = original.copy()  # copy() 메서드를 사용한 복사

 

• 깊은 복사 (Deep Copy)
  • 리스트 내 모든 객체를 재귀적으로 복사
  • 원본과 완전히 독립적인 복사본

import copy

original = [[1, 2], [3, 4]]
deep_copy_list = copy.deepcopy(original)  # 깊은 복사

---

stack 문제집(https://www.acmicpc.net/workbook/view/7309) 풀면서 익혀봅시다.

 

 

✘ 백준 10828 스택 

 

• 간단한 스택 사용 문제

import sys
input = sys.stdin.readline

n = int(input())
stack = []

for _ in range(n):
    command = list(input().strip().split())
    if command[0] == "push":
        stack.append(int(command[1]))
    elif command[0] == "pop":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif command[0] == "size":
        print(len(stack))
    elif command[0] == "empty":
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == "top":
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

최근에 코드 챗 지피티한테 피드백 받는 좋은 습관이 생겼습니다 ㅎㅎ

 

• if-else 구조를 삼항 연산자로 처리하는 부분, 익숙해져서 좀더 코드 간결하게 쓰면 좋을 듯
  
  

import sys
input = sys.stdin.readline

n = int(input())
stack = []

for _ in range(n):
    command = input().split()
    if command[0] == "push":
        stack.append(int(command[1]))
    elif command[0] == "pop":
        print(stack.pop() if stack else -1)
    elif command[0] == "size":
        print(len(stack))
    elif command[0] == "empty":
        print(0 if stack else 1)
    elif command[0] == "top":
        print(stack[-1] if stack else -1)

---

✘ 백준 1874 스택 수열

import sys
input = sys.stdin.readline

n = int(input())
# 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지
nums = [int(input()) for _ in range(n)]
i = 1
stack = []
result = []

for num in nums:
    while i <= n:
        if stack and stack[-1] == num:
            break

        stack.append(i)
        i += 1
        result.append("+")

        if i == num+1:
            break

    if stack[-1] == num:
        stack.pop()
        result.append("-")


if result.count("-") != n:
    print("NO")
else:
    for r in result:
        print(r)

 

 

• while i <= num로 수정: n까지의 범위 전체를 검사할 필요가 없음
• 빠른 실패 처리: stack[-1] != num일 때 수열을 만들 수 없다는 것을 바로 판단하여 NO를 출력
• 출력 간단하게: " ".join(list)
  
  

 

import sys
input = sys.stdin.readline

n = int(input())
nums = [int(input()) for _ in range(n)]

i = 1
stack = []
result = []

for num in nums:
    while i <= num:
        stack.append(i)
        i += 1
        result.append("+")

    if stack and stack[-1] == num:
        stack.pop()
        result.append("-")
    else:
        print("NO")
        break
else:
    print("\n".join(result))

---

✘ 백준 2493 탑

import sys
input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))
answer = [0] * n
stack = []

for i in range(n):
    while stack and stack[-1][1] <= towers[i]:
        stack.pop()

    if len(stack) != 0:
        answer[i] = stack[-1][0]+1

    stack.append([i, towers[i]])

print(" ".join(map(str, answer)))

 

 

• 비어있는 경우 확인할 때) if len(stack) != 0: 대신 if stack:
• 튜플은 리스트보다 메모리 효율 good: stack.append([i, towers[i]]) 대신 stack.append((i, towers[i]))로 
• 가독성 향상: stack[-1][0]와 stack[-1][1] 이런식으로 작성할 땐 주석으로 추가 설명

 

import sys
input = sys.stdin.readline

n = int(input())
towers = list(map(int, input().split()))
answer = [0] * n
# 0: index, 1: tower height
stack = []

for i in range(n):
    while stack and stack[-1][1] <= towers[i]:
        stack.pop()

    if stack:
        answer[i] = stack[-1][0]+1

    stack.append((i, towers[i]))

print(" ".join(map(str, answer)))

 

---

 

3015, 6549 풀다가 우매함 자각의 늪에 빠져서 다음에 풀어서 올리겠습니다...