개발공부일지

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

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

트리(Tree)노드와 링크로 구성된 자료구조(그래프의 일종, Cycle 없음)계층적 구조를 나타낼 때 사용폴더 구조(디렉토리, 서브 디렉토리)조직도, 가계도..  트리의 구조노드(Node): 트리 구조의 자료 값을 담고 있는 단위엣지(Edge): 노드 간의 연결선(=link, branch)루트 노드(Root): 부모가 없는 노드, 가장 위의 노드잎새 노드(Leaf): 자식이 없는 노드 (=단말)내부 노드(Internal): 잎새 노드를 제외한 모든 노드부모(Parent): 연결된 두 노드 중 상위의 노드자식(Child): 연결된 두 노드 중 하위의 노드형제(Sibling) 같은 부모를 가지는 노드깊이(Depth): 루트에서 어떤 노드까지의 간선의 수레벨(Level): 트리의 특정 깊이를 가지는 노드 집합..