그래프란? 그래프는 노드와 간선으로 구성된 자료구조입니다. 간선은 노드를 직접 연결하며 방향의 유무와 단방향, 양방향에 의해 다양한 종류로 나눌 수 있습니다. 그래프의 구현 방법 인접 행렬 2차원 배열을 사용하여 두 노드간의 관계를 0과 1로 표현하는 방식 (노드 간 직접 연결 되어있으면 1, 아니면 0) 인접 리스트에 비해 구현이 쉬우며 모든 노드들의 간선 정보가 있기 때문에 간선의 존재 여부를 확인할 때 O(1)의 시간복잡도를 가집니다. 무조건 2차원 배열이기 때문에 메모리가 낭비될 수 있습니다. 인접 리스트 각 노드마다 직접 연결된 모든 노드들의 리스트를 저장하는 방식 노드들의 연결 정보를 탐색할 때 O(n)의 시간복잡도를 가지며 메모리 사용량이 적습니다. 인접 행렬보다 구현이 어렵고 간선의 존재 ..
HashSet 이란? HashSet은 Set 인터페이스를 구현한 구현한 자료구조로, 중복된 데이터를 허용하지 않는 특징을 가집니다. HashSet 기본 원리 HashSet은 값을 저장할 때 내부적으로 HashMap을 사용하며 키로 사용할 객체와 함께 저장합니다. 값은 기존에 존재하는 동일한 객체를 나타내는 상수를 사용합니다. 이를 통해 HashSet은 중복된 데이터를 저장하지 않는 고유한 특성을 가집니다. HashSet 연산 삽입 : add(element) 삭제 : remove(element) 데이터 들어있는지 확인 : contains(element) 크기 확인 : size() 비어있는지 확인 : isEmpty() 전체 출력 : iterator() 또한 for(T element : set)으로 출력 Ha..
HashMap이란? HashMap은 Hash Table을 구현한 Map으로 여러 개의 키-값 쌍을 빠른 검색과 삽입, 삭제가 가능한 자료구조입니다. HashMap 기본 원리 HashMap은 내부적으로 배열을 사용하여 해시 버킷에서 데이터를 관리합니다. 해시 함수는 키를 해시값으로 변환해주는 역할을 합니다. 이 해시값은 배열의 인덱스로 사용되며, 여러 키가 동일한 해시값을 갖지 않도록 최대한 분산되어 값이 저장될 수 있습니다. HashMap 연산 삽입 : put(Key, Value) 삭제 : remove(Key) 검색 : get(Key) 크기 : size() 비어있는지 확인 : isEmpty() 키가 있는지 확인 : containKey(Key) 모든 키 검색 : KeySet() HashMap 장점 Hash..
해시테이블이란? 해시테이블은 키-값 쌍을 저장하고 검색하는 데 특화된 자료구조입니다. 키를 사용하여 값을 빠르게 검색할 수 있도록, 해시 함수를 이용해 키를 인덱스로 변환하여 값을 저장합니다. 이 과정에서 해시 충돌이 일어날 수 있는데 이를 해결하기 위해 개방 주소법이나 폐쇄 주소법을 사용할 수 있습니다. ※ 해시 충돌 : 해시테이블에서 서로 다른 두 개의 키가 같은 해시 함수 값을 가지는 상황을 의미합니다. 해시테이블 작동 원리 해시 함수 : 키를 인덱스로 변환하기 위해 해시 함수를 사용합니다. 해시 함수는 키의 데이터를 정수 형태의 해시 값으로 변환하여 테이블 내 값의 위치를 저장합니다. 해시 충돌 해결 1. 개방 주소법 : 충돌이 발생한 경우, 빈 슬릇 발견할 때 까지 인덱스를 늘려 충돌을 해결하는..
Heap이란? Heap은 이진 트리를 기반으로한 자료구조로 부모 노드와 자식 노드 간의 순서 관계를 유지합니다. Heap은 순서 관계에 따라 최대 힙(Max Heap), 최소 힙(Min Heap) 두 가지로 나눠집니다. 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 루트는 항상 최대값이 있습니다. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 루트는 항상 최솟값이 있습니다. Heap의 기본 연산 삽입 : 새로운 원소를 삽입하는 경우 힙의 속성을 유지하기 위해 트리를 재구성하는 과정이 포함되기 때문에 O(logN)의 시간 복잡도를 가집니다. 삭제 : 노드의 값을 삭제하는 경우 힙의 속성을 유지하기 위해 트리를 재구..
Queue란? Queue는 FIFO(First In First Out) 원칙을 따르는 데이터 저장 방식의 자료구조입니다. 데이터가 한쪽 끝에서 삽입되고 반대쪽 끝에서 삭제 및 검색이 됩니다. 이 때 삽입되는 곳을 'rear' 또는 'enqueue' 라고 하며 삭제 및 검색되는 곳을 'front' 또는 'dequeue'라고 합니다. Queue의 기본 연산 1. add(n) : 큐의 rear에 데이터를 추가합니다. 2. poll() : 큐의 front의 데이터를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다. 3. remove() : poll()과 동일하지만 큐가 비어있으면 NoSuchElement 에러를 반환합니다. 4. peek() : 큐의 front의 데이터를 반환합니다. 5. isEmp..
Stack이란? 스택은 데이터를 저장하고 가져오는 작업이 LIFO(Last In First Out) 순서로 이루어지는 자료구조입니다. 이렇게 데이터가 들어오고 나가는 입구가 일정한 위치에서만 이뤄지기 때문에 한쪽 끝에서만 삽입과 삭제가 된다는 점이 스택의 주요 특징입니다. Stack의 기본 연산 1. push(n) : 스택의 제일 위에 데이터를 추가하는 연산입니다. 2. pop() : 스택의 제일 위의 데이터를 제거하고 반환하는 연산입니다. 3. peek() : 스택의 제일 위의 데이터를 반환하는 연산입니다. 4. isEmpty() : 스택이 비어있는지 확인하는 연산입니다. Stack의 장점 간단한 구현 스택은 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있습니다. 빠른 속도 스택에서 데이터를 삽입하..
Linked List란? Linked List는 데이터 요소들이 선형적으로 연결된 자료구조입니다. 각 요소는 Node라고 부르고 노드는 데이터를 저장하는 공간과 이웃 노드를 가르키는 포인터로 구성됩니다. 각 요소들은 물리적 순서가 아닌 포인터를 통해 연결되어 있습니다. Linked List 종류 1. 단일 연결 리스트 : 각 노드가 다음 노드를 가르키는 포인터를 가지고 있는 가장 기본적인 형태 2. 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드를 가르키는 포인터 2개를 가지고 있어 양방향으로 탐색할 수 있는 형태 3. 원형 연결 리스트 : 마지막 노드가 처음 노드를 가르키는 포인터를 가지고 있어 연결 리스트가 원형으로 구성되어 있는 형태 Linked List 장점 동적 크기 크기를 동적으로 조정..
ArrayList란? ArrayList란 배열의 크기를 가변할 수 있는 자료구조 입니다. 일반 배열을 사용하여 구현하되, 배열 크기를 동적으로 조절할 수 있도록 추가되었습니다. 따라서 요소가 추가되거나 제거할 수 있기 때문에 유연하게 크기를 재조정할 수 있습니다. 대부분의 프로그래밍 언어에서는 ArrayList와 같은 동적 배열을 제공하며, Java에서는 ArrayList클래스, Python에서는 list 클래스를 사용할 수 있습니다. ArrayList 특징 동적 크기 조절 배열과 달리 ArrayList는 크기를 동적으로 조절할 수 있습니다. 요소가 추가되거나 제거되면 크기가 자동으로 조정됩니다. 빠른 검색 기본 배열과 마찬가지로 인덱스를 활용하여 요소에 빠르게 접근할 수 있으므로 O(1)의 시간 복잡도..
배열(Array) 이란? 배열은 int, boolean 등 동일한 타입의 데이터 요소들이 나열된 자료구조입니다. 배열은 역속된 메모리 공간에 데이터를 저장하며, 각 요소는 인덱스를 통해 쉽고 빠르게 접근할 수 있습니다. 인덱스는 0부터 시작하며, 대부분의 프로그래밍 언어에서 사용되는 방식입니다. 배열의 특징 고정된 크기 배열은 크기가 고정되어 있습니다. 배열을 선언할 때 메모리 크기가 결정되고, 이후 크기를 변경할 수 없습니다. 만약, 배열의 크기를 변경할 경우에는 새로운 배열은 생성하고 기존 배열을 복사하여 넣어야 합니다. 빠른 검색 배열은 인덱스를 통해 각 요소에 빠르게 접근할 수 있습니다. 원하는 데이터를 인덱스를 통해 즉시 찾으며 O(1)의 시간 복잡도를 가집니다. 데이터 삽입 및 삭제 배열의 크..
