- 오늘의 학습 키워드
스택(Stack)
- 공부한 내용 본인의 언어로 정리하기
- 스택이란?
컴퓨터 과학에서 자주 사용되는 자료구조 중 하나로, 데이터를 저장하고 관리하는 데 사용된다.
"쌓아 올리는" 구조를 가지고 있으며, Push와 Pop 연산을 통해 작동한다.
스택의 중요한 특징은 후입선출(LIFO) 방식으로, 가장 나중에 추가된 요소가 가장 먼저 제거된다.
- Push
새로운 요소를 스택의 맨 위에 추가
- Pop
스택의 맨 위에 있는 요소를 제거하고 반환
- 활용예시
1. 갈호 짝 맞추기
2. 역순 문자열 만들기 : 문자열을 뒤집을 때 스택을 사용하면 간단히 해결할 수 있다.
3. 실행취소(Undo)기능 : 프로그램에서 실행 취소 기능을 구현할 때,
이전 상태를 스택에 저장하여 가장 최근 상태를 쉽게 복원할 수 있다.
- 주요 연산
1. push(item) : 새로운 요초를 스택의 맨 위에 추가
def push(item) :
items.append(item)
2. pop() : 스택의 맨 위에 있는 요소를 제거하고 반환, 비어있으면 'None' 반환
def pop() :
if not is_empty():
return items.pop()
else :
return None
3. is_empty() : 스택이 비어있는지 확인, 비어있으면 True, 아니면 False 반환
def is_empty():
return len(items) == 0:
4. peek() : 스택의 맨 위에 있는 요소를 반환하지만 제거하지 않음, 비어있으면 'None' 반환
def peek():
if not is_empty():
return items[-1]
else :
retrun None
< 오늘의 회고 >
- 어떤 문제가 있었고, 나는 어떤 시도를 했는지
올바른 괄호 문자열인지 확인하는 문제에서 나는
주어진 문자열에서 "()"의 개수가 짝수이면 True를 반환하는 방법으로 시도했다.
def solution(s) :
if s.count('()') % 2 == 0:
return True
else :
return False
그 결과, 기본 테스트케이스는 통과가 되었지만 정확성 테스트에서 실패하였다.
- 어떻게 해결했는지
Chat GPT를 통해 스택구조를 활용하면 된다는 것을 알았다.
def solution(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack:
return False
stack.pop()
retrun len(stack) == 0
이 방법은 시간복잡도가 O(n)으로 효율적이다.