ryureeru의 IT blog

최소 신장 트리 Minimum Spanning Tree (MST) 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 1. 크루스칼 (Kruskal) 간선 중 최솟값을 가진 간선부터 연결한다 (간선들 정렬하고 시작) 사이클이 발생하면 다른 간선을 선택한다 간선 수가 적을 때 사용 알고리즘 복잡도 : O(간선 수 * log(간선 수)) static int parents[]; public int kruskal(int[][] data, int v, int e) { int weightSum = 0; // 간선 가중치 오름차순 정렬 Arrays.sort(data, (x, y) -> (x[2] - y[2])); // union-find 배열 초기화 parents = new int[v + 1]; for (int ..

최단 경로 알고리즘 가중 그래프 상에서 두 노드를 연결하는 가장 짧은 경로를 찾는 방법 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는 데에 사용 1. 다익스트라 (Dijkstra) 한 노드에서 모든 노드로의 최단 경로를 구할 수 있다 간선에 음의 가중치가 없어야 한다 알고리즘 복잡도 : O(간선 수 * log(노드 수)) class Node { int to; int weight; public Node(int to, int weight) { this.to = to; this.weight = weight; } } public void dijkstra(int v, int[][] data, int start) { ArrayList graph = new ArrayList(); for (int i = ..

다이나믹 프로그래밍 (Dynamic Programming) 동적 계획법 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 알고리즘 즉, 답을 찾아가는 과정에서 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식 중간 계산 결과를 기록하기 위한 메모리가 필요 한 번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠름 타뷸레이션(Tabulation) : 상향식 접근 방법 메모이제이션(Memoization) : 하향식 접근 방법 원래 재귀 호출로 구현한 피보나치 수열을 DP를 이용해 구현해보자 public static int fib(int n) { if (n

이진탐색 (Binary Search) 정렬된 상태의 데이터에서 특정 값을 탐색하는 방법 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 찾고자 하는 값이 더 작으/크면 데이터 왼/오른쪽 부분에서 다시 이진탐색 1. 직접 구현하기 public int binarySearch(int arr[], int target) { int left = 0; int right = arr.length - 1; while (left

트라이 (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..