CS/💾 자료구조

자료구조 : 데이터를 저장하고 관리하는 방식 자료구조에서 사용하는 메모리는 크게 HDD 와 RAM 이 존재한다. HDD 는 우리가 코드를 작성하면 저장하는 곳이고 이 코드를 실행하는 곳이 바로 RAM 이다. 이 RAM에 대해서 알아보자 RAM 0과 1로 이루어진 컴퓨터 ( 이진법 ) 램에는 수많은 레지스터가 존재한다. 그 레지스터가 on 일시 1 을 뜻하고 off 가 되면 0 이된다고 쉽게 생각해볼때 한 개의 레지스터는 2개의 수를 나타낼수 있는 것이다. 한개의 레지스터는 이진수를 영어로한 binary digit의 약자 bit 가 되는 것이다. 즉, 한개의 레지스터는 1bit 가 되는 것이다. 이처럼 1bit는 2개의 숫자로 표현하는 이진법을 사용하게 되고 2bit는 4개 나아가 8bit(1byte) 는..

스택(Stack) 스택의 특징 LIFO(후입선출)의 자료구조이다. pop() 을 통해 데이터를 빼고 push()를 통해 데이터를 넣는다. 활용 예시로는 후위표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문 기록, 깊이 우선 탐색(DFS) 가있다 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출형식으로 데이터를 저장한다 데이터를 넣고 빼는데는 O(1)의 시간 복잡도가 필요하다. 재귀적인 특징이 있다 큐(Queue) 큐의 특징 FIFO(선입선출)의 자료구조이다 enqueue와 dequeue로 구성되어있다. 활용예시로는 프린터, CPU task scheduling, Cache 구현, 프로세스 관리, 너비우선 탐색(BFS) 등이 있다. 구현 방식에는 두가지가 있다. Array - Based ..

Java 말그대로 java를 뜻하고 Collections 어떤 일정한 부류의 것을 수집하여 한 공간에 모아놓은 것들을 가공하고 처리할 수 있도록 지원하는 자료구조 FramWork 어떤 문제를 해결하기 위한 뼈대 기본 구조라 하면 우리가 떠올려야 할것은 Interface이다. 인터페이스 자체가 껍데기를 뜻한다. 그럼 자바에서 지원하는 껍데기는 무엇이 있을까? 바로 List, Queue, Set 으로 구성되어 있다 물론 가장 대표적인 것이다. List 의 구현체 ArrayList LinkedList Vetor ( Stack ) Queue 의 구현체 PriorityQueue Deque 의 구현체 ArrayDeque LinkedList ( 또 나오는 이유가 있다 ) Set 의 구현체 HashSet LinkedH..

Array 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다 고정된 저장 공간을 가지고 있다 순차적인 데이터를 저장한다. 이 두가지를 통해 Array의 다양한 특징을 알아보자 고정된 저장 공간을 가지고 있다. 예상보다 적은 데이터를 가지고 있다면 남은 메모리 공간이 낭비가 된다 예상보다 많은 데이터를 가지고 있다면 공간을 변형 시킬수 없기 때문에 데이터를 새로 생성해서 사용해야한다. 순차적인 데이터를 저장한다 인덱스를 기준으로 데이터를 저장하게 되면서 조회(lookup)이 O(1)이라는 굉장히 빠른 시간복잡도를 가진다. 내가 어떤 인덱스에 무슨 데이터가 저장되어있는지 확인하려면 첫번째 인덱스에서 추가적인 횟수만 더해서 확인하면 되기 때문이다. 반대로 삽입, 삭제..

힙은 우선순위 큐가 이용하는 자료구조가 된다. 힙이란? 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조 이말을 뜯어서 말하자면 완전 이진 트리 형태 빠르게 찾기 최댓값 or 최솟값 이 3가지가 충족해야 힙 상태가 만들어진다는것이다. 그럼 완전 이진 트리 부터알아보자 1. 완전 이진트리 이와 같은 구성을 트리 구조라고 부르고 최종 자식노드들을 제외한 각 노드(동그라미)들이 자식을 2개씩(이진) 가지고 있는 것을 완전 이진트리 라고 한다. 완전 이진트리는 약간의 조건이 있다 1. 마지막을 제외한 모든 노드들이 채워져 있어야 한다 2. 모든 노드들은 왼쪽부터 채워져가야 한다.' 이런식으로 힙은 완전 이진 트리가 되어있는것을 기본으로 한다. 구현을 할 때에도 이 이미지를 생각하..