덱 (Deque) 삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있는 자료구조 큐의 장점과 스택의 장점을 합쳐놓은 자료구조이다. 특징 크기가 가변적 중간요소가 삽입, 삭제될 때 , 요소들을 앞/ 뒤로 밀 수 있으므로 vector보다 좋은 성능을 가짐 앞/뒤 삽입 삭제 성능은 좋지만 중간의 삽입/삭제 성능은 좋지 않음 시간복잡도 삽입/삭제 : 원소를 앞,뒤에 삽입하는 경우 : O(1) 탐색 : 원소를 탐색하는 경우 O(1) 인덱스 접근 단점 중간에서 삽입 삭제가 어려움 구현이 어려움

우선순위 큐 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력 되는 방식의 큐 우선 순위 큐 구현 방법 비교 구현 방법 삽입 삭제 순서 없는 배열 O(1) O(n) 순서 없는 연결 리스트 O(1) O(n) 정렬된 배열 O(n) O(1) 정렬된 연결 리스트 O(n) O(1) 힙 O(logn) O(logn) 일반적으로 힙을 이용하여 구현 우선순위가 낮은 데이터가 빠져나오지 못하는 기아현상이 일어날 수 있음 | j3sung.tistory.com/740 [자료구조] 힙 (Heap) 힙 (Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정 j3sung.tistory.com

큐 (Queue) 한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제연산만 이루어지는 FIFO(First In First Out) 형식의 자료구조 큐의 연산 - enqueue : 큐에 데이터를 넣는 작업 - dequeue : 큐에서 데이터를 꺼내는 작업 - front : 데이터를 꺼내는 부분에 데이터를 반환 - rear : 데이터를 넣는 부분에 데이터를 반환 시간복잡도 삽입/삭제 : 원소를 삽입 삭제하는 경우 O(1) 검색 : 탐색을 하려면 원소를 하나하나 꺼내 확인해야 한다. O(n) 선형 큐 일반적인 큐의 형태 push가 될 때 rear(back) 포인터를 하나 증가, pop이 될 때마다 front 포인터를 증가하는 방식으로 구현 큐에 데이터를 넣는 경우: 프론트는 고..

스택이란 한 쪽 끝에서 자료의 삽입과 삭제가 이루어지는 LIFO 형식의 자료구조 스택의 연산 - push(item) 삽입 : 스택에 자료를 넣음 - pop() 삭제 : 스택의 자료를 제거 - top() = peak 읽기 : 스택의 맨 위 요소 반환 - empty() : 스택이 비어있는지 확인 시간복잡도 삽입/ 삭제 : O(1) 맨 위 원소 접근 검색 : O(n) 원소를 꺼내서 확인 과정이 필요

힙 (Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태를 유지 (부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리) 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙(heap)의 구현 힙을 저장하는 표준적인 자료구조는 배열 이다. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 힙에서의 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1..

트리란 트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조 노드가 N개인 트리는 항상 N-1개의 간선을 가짐 트리 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 상위 레벨로 직접 연결된 노드 자식 노드(child node): 하위 레벨로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드 간선(edge): 노드간의 연결선 레벨(level): 깊이가 같은 노드끼리의 집합 높이(height): 가장 긴 루트 경로의 길이 차..

2018 KAKAO BLIND RECRUITMENT (2018 카카오 블라인드 채용 문제) 간단한 구현 문제입니다. 1. 숫자인지 확인 1-1. 현재 숫자가 1이고 다음 숫자가 0인지 확인 (숫자 10 확인) 2. S, D, T에 맞게 1번에서 나온 수를 제곱 처리 3-1. * 인경우 이전에 나온 수를 한번 더 결과값에 더하고 현재 값을 2배로 처리 3-2. # 인경우 현재값에 -1을 곱셈 4. 다음이 숫자이면 현재 값을 결과값에 더하고 이전값에 현재값을 저장, 현재값 초기화. 1~4번 반복 * 숫자가 나왔을 때 결과값에 더해주었으므로 마지막 결과값은 반복문이 끝난 후에 넣어주었습니다. #include #include using namespace std; int solution(string dart) {..

단순 연결 리스트 (Simple List) 시작부분에 head가 있으며 노드에 값과 다음 노드를 가리키는 주소값을 가지고 있습니다. 단방향으로 진행되는 리스트를 의미합니다. 장점 : 추가 삭제시 O(1)의 시간복잡도를 가짐 단점 : 배열이나 트리 구조와는 달리 특정 위치 검색시 O(n) 의 시간이 걸림 이중 연결 리스트 (Doubly List) 양방향으로 이동할 수 있는 리스트로 노드에서 다음 노드를 가리키는 주소값과 이전 노드를 가리키는 주소값 두개를 가지고 있습니다. 양방향으로 이동할 수 있다는 장점으로 데이터를 삭제할 때 이전 노드를 찾기위해 한번 더 탐색을 하지 않아도 됩니다. 단순 - (B를 지우기 위해서 B까지 탐색, B이전에 있는 노드를 찾기위해 A를 찾을때까지 탐색, A와 C를 연결) 이중..