본문 바로가기

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

트라이 (Trie) - 비선형 자료구조 👩‍💻 트라이 (Trie)문자열을 저장하고 빠르게 탐색하기 위한 정렬된 트리 형태의 자료구조 문자열 저장을 위한 메모리가 필요하지만, 탐색이 빠름 *** ✏️ 시간 복잡도 및 생성 복잡도길이가 N인 문자열 탐색의 시간 복잡도 :O(N)생성 복잡도 : O(MN) (M: 문자열 개수) ✏️ 트라이 형태문자열 구성 ex) apple, april, ace, bear, best ✏️ 트라이의 삽입앞서 있는 것과 비교하여 있는 부분은 그대로 따라가서 없는 부분부터 노드를 생성, 문자의 끝 노드는 따로 표기를 해둔다. ✏️ 트라이의 삭제문자를 따라가서 끝쪽에 다다르면, ( apple에서의 e, app에서의 p ) 해당 칠해져있는 노드의 (문자열 끝 노드의) 자식노드가 없으면 색칠한 것을 없앤 후 위로 이동, 그.. 2024. 7. 17.

우선순위 큐 (Priority Queue) - 비선형 자료구조 👩‍💻 우선순위 큐 - Priority QueueQueue지만, FIFO가 아니고, 우선순위가 높은 데이터가 먼저나온다.또한 아래와 같은 조건을 항상 만족한다.모든 데이터에 우선순위가 있다.Dequeue시, "우선순위가 높은 순"으로 나간다.우선 순위가 "같은" 경우는 FIFO로 나온다. ✏️ enqueue, dequeue (삽입, 삭제)우선순위 큐를 위해 만들어진 Heap 자료구조를 이용하여 우선순위 큐를 구현시에는enqueue, dequeue가 최소 힙 및 최대 힙의 삽입 삭제와 같다! ✏️ 우선순위 큐의 구현배열연결 리스트힙 : 일반적으로 힙을 이용하여 우선순위 큐를 구현한다. (자바의 내부 클래스도 힙으로 구현되어 있음)일반적으로 Heap을 이용하여 우선순위 큐를 구현하는데에는 시간복잡도.. 2024. 7. 17.

그래프 - 비선형 자료구조 👩‍💻 그래프 (Graph)정점과 간선으로 이루어진 자료구조 (Cyclic)연결된 정점간의 관계를 표현할 수 있는 자료구조트리와 다른점은 트리는 an cyclic 이라면 그래프는 cyclic이다. ***간선끼리 가중치가 있는 경우도 있다. 그래프의 용도 : 지하철 노선도, 통신 네트워크, ... ✏️ 그래프 구조정점(Vertex) : 각 노드간선(Edge) : 노드와 노드를 연결하는 선 (Link, branch)인접 정접 (Adjacent vertex) : 간선 하나를 두고 바로 연결된 정점정점의 차수 (Degree):무방향 그래프에서 하나의 정점에 인접한 정점의 수무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배진입 차수 (In-degree): 방향 그래프에서 외부에서 오는 간선의.. 2024. 7. 16.

균형 이진 트리 (by 이진 탐색 트리) 👩‍💻 균형 이진 트리란?균형 이진 트리란? 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리이다. ✏️ 이진 탐색 트리의 편향 발생경우 1) 이진 탐색 트리에 삽입 되는 순서 : 20 -> 10 -> 30 -> 5 인 경우에는 균형 이진 트리가 된다.경우 2) 이진 탐색 트리에 삽입 되는 순서 : 5 -> 10 -> 20 -> 30 인 경우에는 사향 이진 트리가 된다. ✏️ Balanced Binary Search Tree노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리 종류 :AVL트리 Red-Black 트리 ✨ AVL 트리노드가 삽입, 삭제 될 때 트리의 균형을 체크하고 유지하는 트리각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지BF[Balance .. 2024. 7. 12.

이진 탐색 트리 (Binary search tree) BST - 자료구조 👩‍💻 Binary search ree란?이진 탐색 트리는 아래의 규칙으로 구성된 이진 트리이다.왼쫀 자식 노드의 키는 부모 노드의 키 보다 작음오른쪽 자식 노드의 키는 부모 노드의 키보다 큼각각의 서브 트리도 이진 탐색 트리를 유지중복된 키를 허용하지 않음✏️ 이진 탐색 트리의 특징이진 탐색 트리 규칙에 의해 데이터가 정렬됨이진 트리에 비해 탐색이 빠름 (균형 유지 필요)균형 상태 : O(logN)불균형 상태 : O(N)✏️ 탐색찾고자 하는 데이터를 루트 노드부터 비교 시작대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동찾는 데이터가 없으면 null 반환어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐 ✏️ 삽입Root 부터 비교 시작 (중복 키 발견 시 노드를 추.. 2024. 7. 3.

java - 비트 연산자 (1L 구체적으로 설명하자면, 이 연산은 숫자 1을 왼쪽으로 i비트만큼 이동시켜서 2의 i제곱을 구하는 방법이다.예를 들어, 다음과 같은 경우를 살펴볼 수 있다.1L 20=12^0 = 120=1).1L 21=22^1 = 221=2).1L 22=42^2 = 422=4).1L 23=82^3 = 823=8).여기서 1L은 long 타입의 숫자 1을 의미하며 비트 연산을 사용할 때, 특히 큰 숫자와 작업할 때 int 대신 long을 사용하는 것이 더 안전하다. 즉, (1L 2^i를 계산하는 간단하고 효율적인 방법이며 비트 연산을 사용하면 곱셈을 사용하지 않고도 이 계산을 빠르게 수행할 수 있다. ✨비트연산들의 종류비트 연산은 빠르고 효율적인 계산을 할 수 있어서, 특히 큰 데이터셋을 처리할 때 유용하다.아래는 .. 2024. 6. 26.

이전 1 2 3 다음

티스토리툴바