자료구조 및 알고리즘/바킹독 정리(9)
-
[바킹독] Deque 정리
바킹독 덱 정리 덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능합니다. 참고로 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가지고 있습니다. 우리가 하스스톤이나 유희왕에서 얘기하는 덱은 Deck라서 발음은 둘 다 덱으로 똑같긴 해도 다른 단어입니다. 아무튼 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮겠습니다. -바킹독- 덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1)입니다. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있습니다. STL stac..
2023.03.03 -
큐 강의 정리
큐(Queue) 스택은 LIFO 큐는 FIFO STL Queue에는 인덱스를 가지고 내부 원소 접근하는 기능이 없어 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조입니다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 됩니다. 공항에서 입국수속을 하는 줄과 같은 상황이라고 볼 수도 있습니다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 합니다. -바킹독- 큐에서 연산의 시간복잡도를 보면 스택처럼 원소의 추가와 제거가 모두 O(1)입니다. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 ..
2023.02.24 -
[바킹독 강의]스택 정리
스택 스택이란 한쪽 끝에서만 넣고 뺄 수 있는 자료구조 구조적으로 먼저 들어온 원소가 나중에 나오게 된다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있습니다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 합니다. 스택은 특정 위치에서만 원소를 넣거나 뺄 수 있게 제한을 둔 대신에 원소의 추가와 제거가 모두 O(1)입니다. 나중에 구현을 같이 해보겠지만 우리가 배열의 끝에서 원소를 추가/제거할 때 시간복잡도가 O(1)이었던 것과 완전 상황이 똑같습니다. 그리고 제일 상단의 원소 확인 또한 O(1)입니다. 대신 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능합니다. -> 그렇지만 응용을 통해서 해당 기능이..
2023.02.15