Algorithm/바킹독의 알고리즘 강의11 덱 덱은 Restricted Structure의 끝판왕 같은 느낌의 자료구조 인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 참고로 자료구조에서의 덱은 deque고, Doble Ended Queue라는 뜻이다. 덱의 성질 1. 원소의 추가/ 제거 O(1) 2. 제일 앞/뒤의 원소확인 O(1) 3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 하지만 특이하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. #include #include using namespace std; int main() { deque dq; dq.push_back(1); dq.push_back(2); for(int i = 0; i < dq.size(); i++) { cout 2021. 4. 14. 큐 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 먼저 들어간 원소가 먼저 나오게 된다. 이를 FIFO(First In First Out) 이라 한다. 큐의 성질 1.원소의 추가O(1) 2. 원소의 제거 O(1) 3. 제일 앞/뒤의 원소 확인 O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 배열로도 가능하고, STL을 사용해도 된다. 2021. 4. 12. 스택 스택(Stack) = 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조. 스택은 구조적으로 먼저 들어간 원소가 제일 나중에 오게되는데, 이런 의미로 FILO(First In Last Out) 자료구조 라고도 부른다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Strcture 라고 부른다. 스택의 성질 1. 원소의 추가가 O(1) 2. 원소의 제거가 O(1) 3. 제일 상단의 원소 확인이 O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/ 변경이 원칙적으로 불가능 ㄴ 원래 스택이라는 자료구조는 원소의 추가/ 제거/ 제일 상단의 원소 확인이라는 기능만 제공하는 자료구조이다. 그래서 STL 에도 이 기능은 없다.. 2021. 4. 12. 연결 리스트 손코딩 문제들 문제 1 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 풀이를 효율적으로 구하는 방법은? 정답 동일한 노드가 나올때까지 계속 다음 노드로 가면 된다. 공간 복잡도 O(1), 시간 복잡도 O(N). 문제 2 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은? 정답 일단 두 시작점 각각에 대하여 끝까지 진행시켜서 각각의 길이를 구한다. 그 후 다시 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜 놓고, 두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진시키면 된다. 공간 복잡도 O(1), 시간 복잡도 O(A+B). 문제 3 주어진 연결 리스트 안에 사이클이 있는지 판단하라. 정답 Floyd's cycle-finding a.. 2021. 4. 12. 연결 리스트 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함. ㄴ 연결 리스트의 구조상 어쩔수 없음. 무조건 k를 거쳐야 하기 떄문. 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1). 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움. 연결 리스트의 종류 단일 연결 리스트 (Singly Linked List) 이중 연결 리스트 (Doubly Linked List) 원형 연결 리스트 (Circular Linked List) 배열 vs 연결 리스트 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간 (Overhead) - O(N) STL List.. 2021. 4. 10. 배열에 0 채우기 좋은 방법 algorithm 라이브러리에 있는 fill() 함수를 사용하자. int a[21]; int b[21][21]; fill(a, a+21,0); for(int i = 0; i < 21; i++) fill(b[i], b[i]+21,0); 2021. 4. 9. 이전 1 2 다음 IT_learning's Commit
