알고리즘 & 자료구조/자료구조 11

비선형 자료구조 - 트라이(Trie)

트라이(Trie)문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조정렬된 트리 구조문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름길이가 N인 문자열 탐색의 시간 복잡도: O(N)생성 복잡도: O(N)M: 문자열 개수  트라이 형태문자열 구성apple, april, ace, bear, best파란색 노드: 문자열의 끝을 표시하는 flag를 나타냄  트라이 - 삽입(1)삽입 문자열: apple 트라이 - 삽입(2)삽입 문자열: april 트라이 - 삽입(3)삽입 문자열: appapp까지 있는 단어의 존재를 표시하기 위해 flag가 필요한 것임  트라이 - 삭제(1)삭제 문자열: applee의 flag 표시를 해제하고 자식 노드들이 없으면 e를 지우고l도 자식노드들이 없으므로 지움p는 flag표시..

비선형 자료구조 - 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)(Priority Queue)우선순위가 높은 데이터가 먼저 나옴 (!= FIFO)모든 데이터에 우선순위가 있음Dequeue 시, 우선순위가 높은 순으로 나감우선 순위가 같은 경우는 FIFO  우선순위 큐 - enqueue, dequeue최소 힙 및 최대 힙의 삭제와 같음    우선순위 큐 - 구현배열 연결 리스트힙    우선순위 큐 자바 코드 구현// 비선형 자료구조 - 우선순위 큐// 연결 리스트를 이용한 우선순위 큐// 자바 기본 PriorityQueueimport java.util.*;public class Main { public static void enqueue(LinkedList list, int data) { int idx = lis..

비선형 자료구조 - 그래프(Graph)

그래프(Graph)정점과 간선으로 이루어진 (Cyclic) (트리와 차이점=> 트리는 Cyclic X)연결된 정점간의 관계를 표혀할 수 있는 자료구조그래프의 용도지하철 노선도, 통신 네트워크, ...  그래프 구조정점(Vertex): 각 노드간선(Edge): 노드와 노드를 연결하는 선(ink, breanch)인접 정점(Adjacent vertex): 간선 하나를 두고 바로 연결된 정점정점의 차수(Degree):무방향 그래프에서 하나의 정점에 인접한 정점의 수무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배진입 차수(In-dgree): 방향 그래프에서 외부에서 오는 간전의 수진출 차수(Out-dgree): 방향 그래프에서 외부로 나가는 간선의 수경로 길이(Path length): 경로를 궝하는..

비선형 자료구조 - 힙(Heap)

힙(Heap)항상 완전 이진 트리 형태 (트리가 마지막 레벨을 제외하고 모든 레벨에서 완전히 채워져 있으며, 마지막 레벨에서는 가능한 한 왼쪽부터 채워지는 것을 의미)중복 값 허용반 정렬 상태최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조최소 힙, 최대 힙  시간 복잡도삽입(Insertion): O(log n)삭제(Deletion): O(log n)최대값/최소값 접근(Peek): O(1)  힙 속성(Heap Property)최대 힙(Max Heap)부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조 (형제 노드(같은 레벨)는 크기 상관X, 중복 값 역시 상관X)루트 노드에는 가장 큰 값이 위치** 루트(Root) ** : 트리 구조에서 최상위 노드를 의미계층적인 데이터 구조로, 노드(Node)..

선형 자료구조 - 해시 테이블(Hash Table)

해시 테이블(Hash Table) = 해시 맵, 해시 표키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조해시 함수(Hash Function)를 사용해 키를 특정 인덱스로 변환하여, 데이터를 효율적으로 저장하고 검색해싱키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 사용 예시:데이터베이스 인덱싱캐시(Cache) 구현집합(Set)과 맵(Map)과 같은 데이터 구조의 내부 구현 장점:빠른 데이터 접근: 평균적으로 **O(1)**의 시간 복잡도로 데이터를 검색할 수 있어, 매우 빠른 데이터 접근을 제공 단점:충돌 관리 필요: 해시 함수가 이상적으로 작동하지 않거나 충돌이 많이 발생할 경우 성능이 저하될 수 있음메모리 사용량: 키와 값을 저장하기 위해 추가적인 메모리 공간이 필요  ..

선형 자료구조 - 데크(Deque)

데크(Deque)양쪽에서 삽입과 삭제가 모두 가능한 자료구조  -Deque : Doubly-ended Queue  -Stack과 Queue를 합친 형태 Double-Ended Queue"라는 이름에서 알 수 있듯이, 일반적인 큐(Queue)와 유사하지만,데크는 양쪽 끝에서 연산을 수행할 수 있는 점에서 차별화 됨  주요 특징양방향 연산: 데크에서는 앞쪽(front)과 뒤쪽(rear) 모두에서 요소를 삽입(insert)하거나 삭제(remove) 가능유연한 활용: 데크는 큐(Queue)와 스택(Stack)으로 모두 활용할 수 있으며, 특정 상황에서는 양쪽 끝에서의 접근이 필요한 알고리즘에 적합순서 유지: 데크는 큐와 마찬가지로 삽입된 요소들의 순서를 유지. 따라서, 순서가 중요한 데이터를 관리하는 데 유용 ..

선형 자료구조 - 큐(Queue)

큐(Queue)한쪽 끝에서 데이터를 삽입(enqueue)하고, 반대쪽 끝에서는 데이터를 삭제(dequeue) 할 수 있는 자료구조  -특정 위치에서만 원소를 넣거나 뺄 수 있음 선입선출(First In First Out;FIFO) 자료구조  -먼저 들어온 데이터가먼저 나가는 구조. 이는 실제 대기열이나 줄을 서는 것과 같은 개념 큐에 삽입된 데이터는 삽입된 순서대로 처리되며, 입력 순서대로 데이터 처리가 필요할 때 사용  -프린터 출력 대기열, BFS(Breath-Fisrt Search = 너비우선 탐색) 등 큐는 일반적인 대기열과 유사한 방식으로 작동하며, 주로 순서대로 처리해야 하는 작업을 관리할 때 사용  큐의 종류큐는 기본적인 FIFO 큐 외에도 다양한 변형이 존재원형 큐(Circular Queu..

선형 자료구조 - 스택(Stack)

스택(Stack)후입선출(Last In First Out; LIFO) 자료구조  -마지막에 들어온 데이터가 먼저 나가는 구조 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용  -ex) 함수 콜 스택, 수식 계산, 인터럽트 처리 등  시간 복잡도삽입(Push): O(1) - 데이터의 삽입이 상수 시간에 이루어짐.삭제(Pop): O(1) - 데이터의 삭제가 상수 시간에 이루어짐 .조회(Peek): O(1) - 스택의 최상단 데이터 조회가 상수 시간에 이루어짐.  스택의 활용 사례괄호 짝 맞추기: 프로그래밍 언어에서 괄호의 짝을 확인할 때, 스택을 사용하여 열린 괄호를 저장하고, 닫힌 괄호가 나올 때마다 짝이 맞는지 확인재귀 함수 호출 관리: 대부분의 프로그래밍 언어는 함수 호출이 일어날 때 스택을 사..

선형 자료구조 - 연결 리스트(Linked List)

연결 리스트(Linked List)-원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조-자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음  연결 리스트의 장점-데이터 공간을 미리 할당할 필요 없음-즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이  연결 리스트의 단점-연결구조를 위한 별도 데이터 공간 필요-연결 정보를 찾는 시간이 필요(접근 속도가 상대적으로 느림)-데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요  연결 리스트의 기본 구조각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이름처럼 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당..

선형 자료구조 - 배열(Array)

배열(Array)동일한 타입의 데이터를 연속적으로 나열한 선형 자료구조많은 수의 데이터를 다룰 때 사용각 데이터를 인덱스와 1:1 대응하도록 구성데이터가 메모리 상에 연속적으로 저장됨   주요 특징고정된 크기: 배열은 선언할 때 크기가 고정되며, 이 크기는 변경할 수 없음, 배열의 크기를 초과하는 요소를 추가할 수 없기 때문에, 필요한 크기를 미리 예상하여 배열을 생성해야 함(초과 시 새로 배열을 생성해야 한단 의미)연속적인 메모리 할당: 배열은 메모리에서 연속적인 공간에 할당되며, 이로 인해 인덱스를 사용해 각 요소에 빠르게 접근 가능인덱스를 통한 접근: 배열의 각 요소는 0부터 시작하는 인덱스를 가지며, 이 인덱스를 통해 O(1) 시간 복잡도로 임의의 요소에 접근 가능동일한 데이터 타입: 배열의 모든..