ryureeru의 IT blog

트라이 (Trie) 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조 문자열 저장을 위한 메모리가 필요하지만 탐색이 so fast 정렬된 트리 구조 class Node { HashMap child; boolean isTerminal; public Node(){ this.child = new HashMap(); this.isTerminal = false; } } 1. 삽입 public void insert(String str) { Node cur = this.root; for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (!cur.child.containsKey(c)) { // key가 없으면 cur.child.put(c, n..

우선순위 큐 (Priority Queue) dequeue할 때, 우선순위가 높은 데이터가 먼저 나옴 우선순위가 같은 경우는 Queue와 동일하게 FIFO!! enqueue, dequeue는 최소/대 힙 삽입, 삭제와 같다 1. 우선순위 낮은 숫자 순 PriorityQueue pq = new PriorityQueue(); pq.add(5); pq.add(7); pq.add(3); pq.add(1); pq.add(9); System.out.println(Arrays.toString(pq.toArray())); // [1, 3, 5, 7, 9] 2. 우선 순위 높은 숫자 순 PriorityQueue pq2 = new PriorityQueue(Collections.reverseOrder()); pq2.add(5..

Heap 최솟값 or 최댓값을 빠르게 찾아내는 자료구조 완전 이진 트리 중복 값 허용 1. 최소 힙 (Min Heap) 부모 노드의 key가 자식 노드의 key보다 작거나 같은 형태 2. 최대 힙 (Max Heap) 부모 노드의 key가 자식 노드의 key보다 크거나 같은 형태 최소 힙 구현하기 1. 삽입 트리의 가장 끝 위치에 데이터 삽입 -> 부모 노드와 key와 비교한 후 작을 경우 부모 자리와 교체 public void insert(int data) { heap.add(data); int cur = heap.size() - 1; while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) { int parent = heap.get(cur / 2); heap.set..

그래프 탐색 1. DFS (깊이 우선 탐색) 각 노드를 방문했는지 체크할 배열과 스택을 이용하여 구현 // 인접행렬 ver. public void dfs(int id) { boolean[] visited = new boolean[this.elemCnt]; Stack stack = new Stack(); stack.push(id); visited[id] = true; while (!stack.isEmpty()) { int tmp = stack.pop(); System.out.print(this.vertices[tmp] + " "); for (int i = 0; i < this.elemCnt; i++) { if (!visited[i] && this.adjMat[tmp][i] == 1) { visited[i]..

AVL 트리 노트가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리 각 노드의 BF (Balance Factor : 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이)를 [-1, 0, 1]만 가지게 하여 균형 유지 균형이 깨진 경우 BF가 +/- 면 왼/오른쪽 서브 트리에 이상 회전 연산 : 단순 회전(LL, RR), 이중 회전(LR, RL) 1. LL (Left-Left) 회전 1회 오른쪽 방향으로 회전 2. RR (Right-Right) 회전 1회 왼쪽 방향으로 회전 3. LR (Left-Right) 회전 2회 RR 회전 후 LL 회전 4. RL (Right-Left) 회전 2회 LL 회전 후 RR 회전 public Node rightRotate(Node node) { Node lNode = n..

이진 트리의 순회 아래는 사용할 트리 구조 (배열 ver.) 1. 전위 순회 (Preorder Traversal) public void preOrder(int idx) { System.out.println(this.arr[idx]); int left = idx * 2 + 1; int right = idx * 2 + 2; if (left 왼쪽 노드 -> 오른쪽 노드 출력 : 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 2. 중위 순회 (Inorder Traversal) public void inOrder(in..

해시 테이블 Key, Value을 대응시켜 저장하는 데이터 구조 해싱 : Key를 특정 계산식(Hash function)에 넣어 나온 결과를 사용해 값에 접근하는 과정 해시 충돌 : 해시 테이이블의 같은 공간에 서로 다른 값을 저장하려는 경우 1. 개방 주소법 해시 충돌 시, 테이블에 비어 있는 공간의 해시를 찾아 데이터를 저장 선형 탐사법 : 빈 공간을 순차적으로 탐사하는 방법, 일차 군집화 문제 발생 public void setValue(int key, int data) { int idx = this.getHash(key); if (this.elemCnt == this.table.length) { System.out.println("full"); } else if (this.table[idx] == ..

Deque 기본 구조 양방향에서 삽입, 삭제 가능 Deque 클래스 import java.util.ArrayDeque; import java.util.Deque; Deque deque = new ArrayDeque(); // Front 부분 입력 deque.addFirst(3); deque.addFirst(2); deque.addFirst(1); System.out.println(deque); // [1, 2, 3] // Rear 부분 입력 deque.addLast(4); deque.addLast(5); deque.addLast(6); System.out.println(deque); // [1, 2, 3, 4, 5, 6] // Front 부분 출력 System.out.println(deque.remove..

배열을 이용한 기본 큐 직접 구현 (원형 큐) 1. 큐가 empty할 때 front == rear 일 때, isEmpty는 true 2. 큐가 full일 때 front == (rear+1)%(arr.length) 일 때, isFull은 true Queue 클래스 import java.util.Queue; Queue queue = new LinkedList(); # enqueue queue.add(1); queue.offer(2); System.out.println(queue); # dequeue queue.poll(); System.out.println(queue); System.out.println(queue.size()); System.out.println(queue.isEmpty()); queue...