본문 바로가기

알고리즘/자료구조 이론16

자료구조 목록 (+java에서의 사용) 자료구조에는 크게 선형자료구조와 비선형 자료구조가 있으며 아래는 기본적으로 사용하는 자료구조들의 간략한 설명이다.각 자료구조의 자세한 설명은 해당 블로그 다른글에 서술 되어있다. 💫기본적인 자료구조 모음1. 배열(Array)설명: 동일한 타입의 요소들이 연속된 메모리 공간에 저장된 자료구조입니다.특징: 인덱스를 통해 빠르게 접근 가능, 크기가 고정되어 있음.사용 예: 정수 배열, 문자 배열 등.2. 연결 리스트(Linked List)설명: 각 요소가 노드로 구성되고, 각 노드는 데이터와 다음 노드에 대한 포인터를 가집니다.특징: 동적 크기, 요소 삽입/삭제가 용이함, 임의 접근이 비효율적.사용 예: 리스트, 큐, 스택 구현.3. 스택(Stack)설명: 후입선출(LIFO, Last In First Ou.. 2024. 6. 25.

힙(Heap) - 자료구조 👩‍💻 Heap 이란?비선형 자료구조로 트리 기반의 자료구조이다. 최대 힙(Max Heap), 최소 힙(Min Heap)이 있다. 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같다.Heap은 완전 이진 트리(Complete Binary Tree) 기반으로 만들어졌으며 이진 힙(Binary Heap)은 가장 일반적인 형태이다.우선순위 큐를 위하여 만들어졌으므로 우선순위 큐를 구현할 때 사용되며 최대값이나 최소값을 빠르게 찾을 수 있다. 힙은 일종의 반 정렬 상태를 유지한다.(큰 값이 상위 레벨에 있거나 작은 값이 하위 레벨에 있다. )또한 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 즉, 힙은 최.. 2024. 6. 22.

트리(Tree) - 비선형 자료구조 👩‍💻 Tree란?노드(NODE) + 에지(EDGE)로 구성된 자료구조로 그래프의 일종이라고 볼 수 있다.계층적인 구조를 나타낼때 사용한다. (폴더구조-디렉토리, 조직도, 가계도 등) ✏️ 트리의 특징하나의 노드에서 다른 노드로 이동하는 경로는 유일하다.노드가 N개인 트리의 에지수는 N-1개이다.Acyclic하다. (Cycle이 존재하지 않음)모든 노드는 서로 연결되어 있다.하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다. ✏️ 트리의 구조노드(Node) : 트리 구조의 자료값을 담고 있는 단위에지(Edge) : 노드간의 연결선 (=link, branch)루트노드(Root) : 부모가 없는, 최상단 노드잎새노드(Leaf) : 자식이 없는, 단말 노드내부노드(internal) : 잎새노드를 .. 2024. 6. 22.

Linked List - 자료구조 👩‍💻 Linked List 란?Linked List란 선형자료구조 중 하나로 Node(노드)들이 서로 연결된 형태로 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가진다. 주요 형태로는 단일 연결리스트, 이중 연결리스트, 원형 연결 리스트가 있다.해당 노드들은 물리적으로는 연결되어 있지 않지만, 논리적으로는 포인터를 통해 연결되어 있다. * 삽입과 삭제가 빈번한 상황에서 사용된다. 특히 리스트의 시작이나 끝 부분에서의 삽입 삭제가 효율적이다. ✏️ 시간 복잡도삽입 삭제시 : O(1) ㄴ 따라서 삽입과 삭제가 빈번한 상황에서 많이 사용된다.중간에서의 검색 : O(n) ✏️ 여러가지 Linked List 1. 단일 연결 리스트 (Singly Linked List)단일 연결 리스트에서 각 노드는 다.. 2024. 6. 21.

HashMap - 자료구조 목차 1. HashMap이란?2. 해싱3. 버킷4. 충돌처리 방법 4-1) 체이닝 4-2) 오픈 어드레싱 4-2-1) 선형탐사 4-2-2) 이차탐사 4-2-3) 이중해싱5. HashMap의 주요 메소드6. 성능 특성 (시간복잡도 / 공간복잡도)7. HashMap VS HashTable8. 문제풀이 👩‍💻 HashMap 이란? HashMap 은 Key와 Value가 쌍을 이뤄 저장되는 형태의 자료구조이다.각 key는 고유하여 중복된 값을 가질 수 없으며 key를 사용하여 해당하는 Value에 접근하는 방식이다. ✏️ 해싱 (Hashing)* Hash Map의 핵심이 되는 원리로 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정이다.(해시 함수를 사용하여 키를 해.. 2024. 6. 20.

Array(배열) - (선형)자료구조 Array (배열)은 같은 타입의 데이터를 여러개 나열한 선형 자료구조이다.연속적인 메모리 공간에 순차적으로 데이터를 저장한다. ✏️ Array의 시간 복잡도인덱스를 알고 있는 경우 요소에 접근하는 시간 복잡도 : O(1)ㄴ 배열은 인덱스를 이용하여 원하는 위치에 빠르게 접근 가능하다.삽입 삭제시의 시간 복잡도 : O(n) ㄴ 삽입, 삭제시 해당 위치 이후의 모든 요소들을 이동시켜야하므로 성능이 좋진 않다. ✏️ Array의 장점구현이 쉽다.인덱스를 통해 접근하므로 접근(검색)이 빠르다.연속된 메모리 공간에 저장하므로 메모리 공간을 효율적으로 관리할 수 있다.또한 순서대로 저장되므로 인접한 요소들에 대한 캐시 지역성이 좋아 성능 향상에 도움을 줄 수 있다. 참조를 위한 추가 메모리가 필요하지 않다. 다.. 2024. 6. 19.

이전 1 2 3 다음

티스토리툴바