1. 정의와 성질 덱 - 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조 덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가진다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로 스택과 큐를 덱의 특수한 경우이다. 덱의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL st..

1. 정의와 성질 큐 - 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택은 FILO(First In Last Out), 큐는 FIFO(First in First Out)이다. 큐의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 앞/뒤의 원소 확인 - O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서는 추가되는 곳을 rear, 즉 뒤쪽이라고 하고 제거되는 쪽을 front, 즉 앞쪽이라고 한다. 스택과 ..

1. 정의와 성질 스택 - 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조 먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조이다. +) 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있어 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 스택의 성질 1. 원소의 추가 - O(1) 2. 원소의 제거 - O(1) 3. 제일 상단의 원소 확인 - O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. 원칙적으로 불가능하다는 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 제일 상단이 아닌 나..

1. 정의와 성질 연결 리스트 - 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결 리스트의 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소 추가/제거 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 연결 리스트 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간..

1. 정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 3. Cache hit rate가 높음 4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 2. 기능과 구현 기능 1. 임의의 위치에 있는 원소를 확인/변경 = O(1) 2. 원소를 끝에 추가 = O(1) 3. 마지막 원소를 제거 = O(1) 4. 임의의 위치에 원소 추가/제거 = O(N) 구현 - insert, erase 함수 수정 전 코드 #include using namespace std; void insert(int idx, int num, int arr[], int &len) { len..