스택
책을 쌓듯이 데이터를 쌓은 형태의 자료구조
늦게 들어간 데이터가 먼저 나오는 LIFO(Last In First Out) 특성을 가짐
top: 데이터의 삽입과 삭제가 일어나는 곳
push: 데이터 삽입 연산
pop: 데이터 삭제 연산
peek: top 포인터가 가리키는 데이터를 조회
배열, 연결 리스트로 구현 가능
사진 출처: 위키백과
스택 구현
class Stack:
def __init__(self, size):
self.items = []
self.size = size
def display(self):
print(self.items)
def is_empty(self):
if len(self.items) == 0:
return True
return False
def is_full(self):
if len(self.items) == self.size:
return True
return False
def push(self, item):
if not self.is_full():
self.items += [item]
self.display()
else:
print("데이터를 넣을 저장공간이 부족합니다.")
def pop(self):
if not self.is_empty():
del self.items[-1]
self.display()
else:
print("삭제할 데이터가 없습니다.")
def peek(self):
return self.items[-1]백트래킹
완전 탐색을 통해 해를 찾아가는 중, 현재의 경로가 해가 되지 않을 것 같다면 그 경로를 더 탐색하지 않고 되돌아가는 방법
가지치기라고도 불린다.
- 반복문의 횟수를 줄일 수 있다.
=> 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만을 탐색하는 방법
의사 코드(pseudocode)
def 재귀함수(n):
if 정답이면 :
출력 or 저장
else : 정답이 아니면 :
for 모든 자식 노드에 대해서:
if 유망하다면(답의 가능성이 있으면) :
자식노드로이동
재귀함수(n+1)
부모노드로 이동