❒ Description날짜2024.09.29 (일)레벨Medium제목Largest Number링크https://leetcode.com/problems/largest-number/description/알고리즘삽입 정렬시간 복잡도O(NlonN)    ❒ 문제 및 로직 분석요구사항 : 주어진 배열을 가장 큰 하나의  숫자로 반환하라. 주어진 두 수 a,b를 더해서 비교해야 한다. ab 와 ba를 비교 후 내림차순 정렬     ❒ Solutionpublic String largestNumber(int[] nums) { String[] numsStr = new String[nums.length]; for (int i = 0; i { @Override public int compare(S..

❒ Description삽입 정렬의 구현방법을 정리하자.     ❒ Insertion sort 1. 동작 방식삽입 정렬은 target 값과 그 이전 요소들을 비교하면서, `target 인 경우에 swap하는 방식이다.   2. 특징내부 정렬 : 추가적인 배열을 사용하지 않고 원래 배열 내에서 정렬이 이루어진다.안정 정렬 : 같은 값의 원소들 간의 순서가 보존된다.온라인 정렬 : 정렬 과정 중 새로운 데이터를 처리할 수 있다. 3. 장단점장점거의 정렬된 데이터에서 매우 효율적이다.적은 데이터에 적합하다.추가 메모리 사용이 없다.단점비효율적 : 대규모 데이터에서는 비효율적이다.데이터가 역순의로 정렬된 경우 성능이 저하된다. 4. 시간 복잡도BestO(n)AverageO(n²)WorstO(n²)     ❒ ..

❒ Description날짜2024.09.27 (금)레벨Medium제목Insertion Sort List링크https://leetcode.com/problems/insertion-sort-list/description/알고리즘정렬시간 복잡도O(NlonN) 이번 문제는 삽입 정렬을 구현하면 되는 문제이다. 하지만 기본적으로 Linked List가 주어지기 때문에 까다롭다.     ❒ 문제 및 로직 분석먼저 삽입 정렬은 정렬을 해야 할 대상과 정렬을 끝낸 대상, 두 그룹으로 나눠야 한다.sorted : 정렬을 끝낸 대상head : 정렬을 해야 할 대상그리고 몇가지 특이 케이스를 고려해야 한다. 1. 정렬된 결과 사이에 삽입해야 할 경우위 경우와 같이 `sorted.next.val = 3` 이 정렬되어야 할 ..

❒ Description날짜2024.09.27 (금)레벨Medium제목Merge Intervals링크https://leetcode.com/problems/merge-intervals/description/알고리즘정렬시간 복잡도O(NlonN)      ❒ 문제 및 로직 분석이번 문제는 겹치는 구간을 판단하는 아이디어가 필요한 문제이다.int[][] intervals = { {1, 3}, {8, 11}, {2, 6}, {15, 18} }i번 째 배열의 1번 째 요소와 i + 1 번째 배열의 0번 째 요소를 비교하면 겹침 여부를 판단할 수 있다.※ 겹치는 경우i 번째 배열의 1번 째 요소 >= i + 1 번째 배열의 0번 째 요소Range1과 Range2가 겹치는 범위인지 판단겹치는 경우라고 판단이 됐다면, ..

❒ Description날짜2024.09.27 (금)레벨Medium제목Sort List링크 https://leetcode.com/problems/sort-list/description/자료구조 알고리즘정렬시간 복잡도O(nlogn)     ❒ 문제 분석시간 복잡도 O(nlogn) 으로 풀어야하는 제약이 있는 문제다. 따라서 병합 정렬을 사용해야 한다.먼저 병합 정렬의 분할 정복을 위해서는 중앙을 분리해야 한다. 이 문제는 LinkedList를 사용하고 있고,이 자료 구조는 배열의 길이를 알 수 없다. 따라서 Runner 기법을 사용해야 한다. 마지막에는 정복(Conquer)하는 과정이 필요한데, 이 때 오름차순으로 정복해야 한다.1c1 = `-1 > 5`c2 = `0 > 3 > 4`c1.val > c2.v..

❒ Description날짜2024.09.26 (목)레벨Medium제목Construct BT from Preorder and Inorder Traversal링크https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/자료구조그래프 - BST시간 복잡도O(n)      ❒ 문제 및 로직 분석int[] preorder = {1, 2, 4, 5, 3, 6, 7, 9, 8}; // 전위 순회int[] inorder = {4, 2, 5, 1, 7, 9, 6, 8, 3}; // 중위 순회 전위 순회의 첫 번째 값은 항상 root 노드다. 즉, 전위 순회의 첫 번째 결과는 정확히 중위 순회 결과..

❒ Description트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 Binary Tree에서 DFS는노드의 방문 순서에 따라 크게 3가지 방식으로 구분된다.  오늘은 이 3가지 방식에 대해서 학습해볼 것이다.     ❒ 전위 순회 (Pre-Order) : Root > Left  > Right전위 순회는 Root > Left > Right 순으로 노드를 방문하는 방법이다.더보기preorder(node) if (node == null) return visit(node) preorder(node.left) preorder(node.right)더보기pu..

❒ DescriptionConcurrency Control은 트랜잭션이 동시에 실행될 때 발생할 수 있는 여러 문제를 해결하면서, Isolation 수준을보장하는 데 중요한 역할을 한다. 이 내용은 앞선 두 포스팅에서 학습하였다.  ※ 앞선 학습 내용DB Transaction & Concurreny Control (1)DB Transaction & Concurreny Control (2) 오늘은 Concurrency Control 방법론을 통해 구현(보장)되며, 다수의 트랜잭션이 동시에 실행될 때 트랜잭션간의 간섭을 제어하여 데이터의 일관성을 유지하고, 각 트랜잭션이 독립적으로 수행되는 것처럼 보이게 하는 속성인isolation에 대해서 더 자세히 학습할 예정이다.     ❒ Isolation 이상 현상..

❒ Description날짜2024.09.25 (수)레벨Easy제목Minimum Distance Between BST Nodes링크https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/자료구조그래프 - BST시간 복잡도O(n) [LeetCode#1038] Binary Search Tree to Greater Sum Tree 문제와 거의 유사한 문제이다.     ❒ Solutionprivate int prev = Integer.MIN_VALUE + 10000;private int minDiff = Integer.MAX_VALUE;public int minDiffInBST(TreeNode root) { if (root ..

❒ Description날짜2024.09.25 (수)레벨Easy제목Range Sum of BST링크 https://leetcode.com/problems/range-sum-of-bst/description/자료구조BST     ❒ 문제 분석트리에서 부모노드 보다 작은 노드는 왼쪽으로, 큰 노드는 오른쪽에 위치한다. 이번 문제에서는 가장 작은 값 low와가장 큰 값 high를 제시해준다. 따라서 재귀 구조로 트리를 순회할 때 현재 노드의 값이 low 보다 작다면 오른쪽만탐색하고, 현재 노드의 값이 high 보다 크다면 왼쪽만 탐색한다. root root > high : 왼쪽만 탐색    ❒ Solution1. 트리의 특징을 통한 문제해결public int rangeSumBST(TreeNode root, i..