Study for Backend/Data Structure (21) 썸네일형 리스트형 [Data Structure 기초] 트라이 Trie (트라이) - 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조 - 정렬된 자료구조 - 문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름 - 음의 간선이 포함되어 있어도 사용 가능하나 음수 사이클이 있으면 정상 동작 하지 않음 알고리즘 복잡도 : O (N) // 비선형 자료구조 - 트라이 (Trie) import java.util.HashMap; class Node { HashMap child; // 단어 끝인지 체크 용 boolean isTerminal; public Node() { this.child = new HashMap(); this.isTerminal = false; } } class Trie { Node root; public Trie() { this.root = new.. [Data Structure 기초 연습] 우선순위 큐 - 오름차순 정렬 02 // 비선형 자료구조 - 우선순위 큐 // Practice 2 // 나이 오름차순 (인터페이스 상속 구현 없는 버전) import java.util.PriorityQueue; class Person3 { String name; int age; public Person3(String name, int age) { this.name = name; this.age = age; } } public class priorityQueuePractice03 { public static void solution(String[] name, int[] age) { PriorityQueue pq = new PriorityQueue(); } public static void main(String[] args) { String[.. [Data Structure 기초 연습] 우선순위 큐 - 오름차순 정렬 01 // 비선형 자료구조 - 우선순위 큐 // Practice 1 // 나이 순으로 오름차순 또는 내림차순 출력 // 자바 기본 PriorityQueue import java.util.PriorityQueue; class Person2 implements Comparable { String name; int age; public Person2(String name, int age) { this.name = name; this.age = age; } @Override public int compareTo(Person2 o){ // 1 : 변경 안함. 우선순위가 높지 않음 // -1 : 변경 //새롭게 추가하는 데이터가 더 적을 때 변경 (적은 값이 위로 올라감) return this.age >= o.age ?.. [Data Structure 기초] 우선순위 큐 Priority Queue (우선순위 큐) - 우선순위가 높은 데이터가 먼저 나옴 - 모든 데이터에 우선순위가 있음 - Dequeue 시 , 우선수위가 높은 순으로 나감 - 우선 순위가 같은 경우는 FIFO - 최소 힙 및 최대 힙의 삽입 삭제가 같다 - 배열, LinkedList, Heap 으로 구현 가능 시간 복잡도 비교 // 비선형 자료구조 - 우선순위 큐 // 연결 리스트를 이용한 우선순위 큐 // 자바 기본 PriorityQueue import java.util.*; public class Main { public static void enqueue(LinkedList list, int data) { int idx = list.size(); for (int i = 0; i < list.size(.. [Data structure 기초 연습] ArrayList로 최소/최대 힙 구현 import java.io.IOException; import java.util.ArrayList; //비선형자료구조 힙 //ArrayList로 최소 힙 구현 class MinHeap{ ArrayList heap; public MinHeap(){ this.heap = new ArrayList(); this.heap.add(0); } public void insert(int data){ heap.add(data); int cur = heap.size() - 1; //insert 하는 곳 while (cur > 1 && heap.get(cur / 2) > heap.get(cur)){ //비교 int parentVal = heap.get(cur / 2); heap.set(cur / 2, data);//스왑 h.. [Data Structure 기초] 그래프와 트리의 차이 Graph (그래프) Trees (트리) 개요 노드와 간선으로 이루어진 자료 구조 그래프의 한 종류 방향성 방향 그래프, 무방향 그래프 방향 그래프 사이클 Cyclic Acyclic 모델 네트워크 모델 계층 모델 루트 노드 루트 노드 X 최상위 노드 부모-자식 부모-자식 관계 X 인접한 상하위 노드 간선 수 그래프에 따라 간선 개수 다름 N개의 노드로 구성된 트리의 간선 수는 N-1개 순회 DFS , BFS Pre-, In-, Post-order / Level-order 경로 2개 이상의 경로 가능 두 노드 간의 경로는 1개 [Data Structure 기초] 그래프 그래프 (Graph) - 정점과 간선으로 이루어진 자료구조 (Cyclic) - 연결된 정점간의 관계를 표현할 수 있는 자료구조 - 그래프의 용도 : 지하철 노선도, 통신 네트워크 등 그래프 구조 용어 정점 (Vertex) 각 노드 간선 (Edge) 노드와 노드를 연결하는 선 ( link, branch ) 인접 정점 (Adjacent vertex) 간선 하나를 두고 바로 연결된 정점 정점의 차수 (Degree) - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수 (In-degree) 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-degree) 방향 그래프에서 외부로 나가는 간선의 수 경로 길이 (Path lengt.. [Data Structure 기초] Tree Tree(트리) - 노드와 링크로 구성된 자료구조(그래프의 일종, Cycle 없음.) - 하나의 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결그래프 - 계층적 구조를 나타낼 때 사용 - 폴더 구조 (디렉토리, 서브 디렉토리) , 조직도, 가계도 등 - 다른 노드로 이동하는 경로는 유일 - 노드가 N개인 트리의 Edge의 수는 N-1개 - Acyclic - 모든 노드는 서로 연결 되어있음 - 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨 트리구조 용어 특징 노드( Node ) 트리 구조의 자료 값을 담고 있는 단위 엣지 ( Edge ) 노드 간의 연결선 ( = link, branch ) 루트 노드 ( Root ) 부모가 없는 노드, 가장 위의 노드 잎새 노드 .. [Data Structure 기초연습] 해시 테이블을 이용한 수 찾기 //20240302 //해시 테이블을 이용한 수 찾기 //주어진 첫 번째 배열을 이용하여 해시 테이블을 초기화 한 후 //두 번째 배열이 주어졌을 때 해당 배열 내 데이터가 해시 테이블에 있는지 확인하는 코드를 작성하세요 import java.util.Hashtable; public class hashTablePractice06 { public static void solution(int[] arr1 , int[] arr2){ Hashtable ht = new Hashtable(); for (int i = 0; i < arr1.length; i++) { ht.put(arr1[i], arr1[i]);//key 와 value 둘다 동일한 값으로 저장 } for (int i = 0; i < arr2.lengt.. [Data Structure 기초연습] HashTable - 해시 충돌 해결 - 분리 연결법 //20240229 //해시 충돌 해결 - 분리 연결법 class Node6{ int key; int data; Node6 next; Node6(){} Node6(int key, int data, Node6 next){ this.key = key; this.data = data; this.next = next; } } class LinkedList6{ Node6 head; LinkedList6(){} LinkedList6(Node6 node){ this.head = node; } public boolean isEmpty(){ return this.head == null; } public void addData(int key, int data){ if(this.head == null){ this.head .. 이전 1 2 3 다음
