전체 글92 Queue 개요 한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조 Queue의 성질 First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다. rear에 삽입하고 front에서 삭제한다. Queue 대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다. 배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다. 아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.) struct Arr.. 2020. 10. 26. Stack 개요 한 쪽 끝에서만 삽입 삭제가 일어나는 자료구조 Stack의 성질 Last-in First-out (LIFO), 즉 후입선출 방식으로 객체를 담는다. 삽입과 삭제에 쓸 위치를 알고 있어야 한다. Stack 대표적인 operation은 push, pop이 있고, 추가로 top, size, empty 등을 지원할 수 있다. Array 또는 Linked List로 구현할 수 있다. 아래는 각각에 대한 예시이다. struct ArrayStack { int* stack; int maxSize, sz; ArrayStack(int ms) { maxSize = ms; sz = 0; stack = new int[maxSize]; } void push(int data); int pop(); } struct Node {.. 2020. 10. 26. Doubly Linked List와 Iterator 개요 노드의 sequence를 담은 자료구조. 더 일반화 된 List ADT를 구현할 수 있다. DLL의 성질 각 노드는 이전 노드와 다음 노드에 대해 양방향으로 연결한다. 두 더미 노드 trailer, header를 활용하면 구현에 용이하다. Node SLL에 추가로 이전 노드의 주소를 가진다. 아래는 앞으로 사용할 노드의 예시이다. struct Node { int data; Node* next; Node* prev; } Doubly Linked List SLL보다 일반적인 함수 구현에 유리하다. 예를 들면, 다음과 같은 ADT를 구성할 수 있다. struct DLL { Node* head; Node* tail; Iter it; void insert(Node* target, int e); void er.. 2020. 10. 26. Singly Linked List 개요 노드의 sequence를 담은 자료구조. Array의 단점인 유연하지 못한 크기 조절을 해소한다. SLL의 성질 각 노드는 다음 노드를 연결하여 단방향 순차 접근이 가능하다. Node 각 노드는 값 (element)과 다음 노드의 주소를 가진다. 아래는 int형 element (data)와 다음 노드의 주소 (next)를 가지는 노드의 예시이다. struct Node { int data; Node* next; } Singly Linked List SLL은 ADT로서 데이터 (노드), Operation (함수)를 가진다. 아래는 노드의 시작 주소 (head)와 간단한 함수들을 가지는 SLL의 예시이다. struct SLL { Node* head; int at(int); bool empty(); voi.. 2020. 10. 26. Array 개요 동일 자료형 원소들의 sequence. TYPENAME name[SIZE] 의 꼴로 쓴다. Array의 성질 index를 이용해 각 원소를 임의 참조할 수 있다. [0 : N) 크기를 미리 정해야 한다. Insertion index i에 원소 e를 삽입할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$ Deletion index i의 원소를 삭제할 때, index가 i 이상인 모든 원소를 shift 한다. $O(n)$ Array의 원소들은 연속하여야 하기 때문이다. Implementation 아래는 이론에서 배운 내용을 구현한 코드이다. #include using namespace std; /* # Insert(i, e)O(n) # Remove(i)O(n) # at(i)O(1.. 2020. 10. 25. Codeforces 블루 (1606점) 달성 #677 Div.3 라운드 192위로 104점 가량이 올라버렸다. 2021년 목표였는데 생각보다 빨리 이루어졌다. 이제 마음 편하게 할 수 있다... 2020. 10. 21. 이전 1 ··· 5 6 7 8 9 10 11 ··· 16 다음
