본문 바로가기

자료구조

 (4)
이진 검색 트리(Binary Search Tree, priorty queue, set, map) Balanced BST(균형이 맞춰져 있는 이진 검색 트리)는 c++에서 heap(priorty queue)와 set으로 구현되어 있고, java에서는 tree set, python에서는 set, dict, tree set 등이 있다. 이진 검색 트리(Binary Search Tree, BST) 바이너리 서치가 중앙값보다 작으면 왼쪽 크면 오른쪽으로 이동했으니깐 똑같은 원리로 이루어진 트리 하지만 이진검색트리 만으로는 균형이 잡혀 있지 않기 때문에 최악의 경우 검색, 삽입, 삭제가 O(N)이 걸린다. 그래서 실제로 BST를 사용하지 않는다. 추가, 삭제, 검색이 O(N)이 걸리기 배열을 사용하겠다,, //이진 검색 트리는 매우 중요한 알고리즘이지만 BST를 구현하는 문제는 거의 없다. 고로 균형이 맞춰져..
자료구조 : 덱(deque) 1. 덱의 정의 덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조 2. 덱의 함수 push_front : 덱의 앞에 데이터를 넣음 push_back : 덱의 뒤에 데이터를 넣음 pop_front : 덱의 앞에서 데이터를 뺌 pop_back : 덱의 뒤에서 데이터를 뻼 front : 덱의 가장 앞에 있는 데이터 back : 덱의 가장 뒤에 있는 데이터 3.덱의 구현 스택과 큐를 합친것과 같음 4.덱 관련 문제 풀이 백준 10866번 덱 : https://www.ac..
자료구조 : 큐(queue) 1. 큐의 정의 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 한쪽 끝에서만 데이터를 넣고 다른 한쪽 끝에서만 데이터를 뺄 수 있다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 2. 큐의 함수 push : 큐에 자료를 넣음 pop : 큐에서 자료를 뺌 front : 큐의 가장 앞에 있는 자료 back : 큐의 가장 뒤에 있는 자료 empty : 큐가 비어있는지 아닌지 size : 큐에 저장되어있는 데이터의 개수 C++의 경우 STL의 queue,..
자료구조 : 스택(Stack) 1. 스택의 정의 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 가장 가까운 값을 O(1)만에 찾아오는 특징이 있다. 2. 스택의 함수 push : 스택에 데이터를 추가 pop : 스택에서 데이터를 삭제 top..

티스토리툴바