본문 바로가기

전체글149

ArrayList 개념에 대해 알아볼게요. ArrayList ArrayList를 알아보기 전에 먼저 Array에 대한 특징을 간략히 살펴보면.. 고정된 크기를 갖는다. (논리) 메모리에 연속적으로 배치되어 있다. 순서가 존재하며 순차적으로 할당된다. 특징을 보면 Array의 가장 큰 한계는 고정된 크기라는 점이다. 배열은 인덱스에 따라서 값을 유지하기 때문에 데이터가 삭제되어도 빈자리가 그대로 남게되어 메모리 낭비가 있다. 빈자리를 채우기 위해 데이터들을 Shift 해야하는 연산 작업이 있다. 따라서 위의 한계를 극복하기 위해 나온 것이 ArrayList이다. 💡 PHP에서는 Array가 고정된 크기가 아닌 데이터 추가시 자동으로 사이즈가 늘어난다. ArrayList 개념 자바에서 ArrayList는 자바 컬렉션 프레임워크중 하나인 List 인터.. 2023. 3. 11.
HashTable이란 뭘까?? Hash Table 만약에 어떤 사람이 유튜브 동영상을 다운로드 받아서 그대로 자신의 영상을 올리게 되면 에러가 발생한다. 바로 중복된 영상이라고 경고를 내리는데 이게 가능한 이유가 Hash Table이다. Hash Table 개념 F(key) -> Hash Code -> Index -> Value Hash Table이란 검색하고자 하는 Key값을 입력받고 입력받은 Key값을 해시 함수를 이용하여 반환받은 Hash Code를 배열의 index로 환산해서 데이터(Value)를 저장하고 접근하는 방식을 Hash Table이라 한다. (위에서 설명한 키워드들을 하나씩 알아보자.) Key값은 문자열이나 숫자, 파일 데이터가 될 수 있다. Hash Table 과정 Hash Table의 가장 큰 장점은 검색 속도가.. 2023. 3. 9.
그래프에 대해 알아보자.(인접행렬과 인접리스트, DFS와 BFS) Graph 앞서 트리 자료구조를 살펴보았다. 트리란 루트 노드가 있고, 부모-자식 관계가 성립하여 계층형 모델이라고 불리며, 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 위에서 아래로 연결되는 사이클이 없는 방향 그래프이다. Graph 개념 위에서 트리를 사이클이 없는 방향 그래프라고 정의했다. 왜 트리가 사이클이 없는 방향 그래프인지 아래 그림을 보자. 위 그림에서 트리가 Edge의 방향을 위로 또는 아래로 조정할 수도 있고, 방향을 아에 가지지 않을 수도 있고, Edge가 자기 자신을 가리키게 할 수도 있고, 방향이 돌고 돌아 노드들끼리 Circle이 형성될 수도 있다?? 만약 위와 같은 트리가 형성되면 굉장히 복잡해지고, 트리를 사용하는 목적이 사라질 것이다. 그래서 위의 그림을 그래프라고 .. 2023. 3. 4.
Heap에 대해 간략히 알아보자. Heap Heap이란 최대값이나 최소값을 구하는데 빠르게 찾아내기 위해 고안된 완전 이진 트리(Complete Binary Tree)를 기반으로 한 자료구조이다. 따라서 Binary Heap(이진 힙)이라고도 한다. Min-Heaps, Max-Heaps Heap에는 2가지가 있다. Min-Heap (최소힙) : 작은 값을 항상 위에 위치하여 최종적으로 가장 작은 값이 root 노드에 위치하게 된다. Max-Heap (최대힙) : 큰 값이 항상 위에 위치하여 최종적으로 가장 큰 값이 root 노드에 위치하게 된다. 최소힙에 노드 삽입 힙에 노드를 삽입할 때는 트리의 맨 끝에 노드를 삽입하게 되는데 삽입할 때 완전 이진 트리의 구조를 잃지 않도록 레벨의 왼쪽부터 채워나가야 한다. 노드를 삽입한 이후에는 정렬.. 2023. 3. 2.
Tree에 대해 알아보기 (종류, Trie) Tree Tree를 이해하기 전에 먼저 선형 구조와 비선형 구조에 대해 알아볼 필요가 있다. 자료구조는 크게 2가지로 분류할 수 있다. 선형 구조 선형 구조란 자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태이다. 즉, 일직선 데이터 구조를 말한다. Array, LinkedList, Stack, Queue가 바로 선형 구조이다. 또한 선형 구조는 자료들의 관계가 1:1 관계가 된다. 비선형 구조 비선형 구조는 하나의 자료에 여러 개의 자료가 존재할 수 있는 형태를 말한다. 트리와 그래프가 바로 비선형 구조이다. 또한 자료들의 관계가 1:N 또는 N:N이 될 수 있다. 비선형 구조의 특징은 부모-자식간의 관계를 갖고 있으며, 계층적 구조를 나타낸다. Tree 개념 선형 구조와 비선형 구조를 알아보았.. 2023. 3. 1.
큐(Queue) Queue 자바에서 Queue는 java.util.Queue를 import하여 사용할 수 있으며, 자바의 Collection 인터페이스를 상속받은 인터페이스이다. 즉, 자바 컬렉션 프레임워크 중 하나이다. 자바에서 Queue를 사용할 때는 인터페이스이기 때문에 아래 코드와 같이 구현체로 LinkedList를 생성해서 사용한다. Queue Q = new LinkedList() Queue 개념 먼저 Queue의 뜻을 검색해보면 "줄을 서는 것" 라는 의미로, 먼저 들어온 데이터가 먼저 나가는 구조의 저장 공간을 말한다. 그림을 보았듯이 Queue는 Stack과는 달리 구멍이 양쪽 끝에 뚫려 있으며, 먼저 들어온 데이터가 먼저 나간다고 해서 FIFO(First In First Out)이라고 한다. Queue에.. 2023. 2. 28.