❒ Description날짜2024.09.25 (수)레벨Medium제목Binary Search Tree to Greater Sum Tree링크 https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/자료구조BST     ❒ 문제 분석 누적 합을 관리해 줄 변수(accumulate)가 필요하다. 우선 주어진 트리에서 값이 가장 큰 노드를 찾아야 한다. (오른쪽 서브트리를 탐색)accumulate에 현재 노드의 값을 갱신해준다. (덧셈)현재 노드의 왼쪽 서브트리를 탐색한다.2~3번 과정을 반복한다. 위 그림에서 작업 순서는 9 > 7 > 6 > 5 > 4 > 3 > 2 > 1 > 0 이 된다.     ❒ Solution..

❒ Description날짜2024.09.25 (수)레벨Easy제목Convert Sorted Array to Binary Search Tree링크https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/자료구조그래프 - BST시간 복잡도O(n)이번 문제는 BST의 특징을 정확하게 파악하고 있어야 한다.     ❒ Solutionpublic TreeNode sortedArrayToBST(int[] nums) { return construct(nums, 0, nums.length - 1);}public TreeNode construct(int[] nums, int lo, int hi) { if (lo >..

❒ Description Subent, Subnet Mask 그리고 Subnetting의 정의에 대해서 알아보고, 서브넷팅 계산하는 법도 공부하자!     ❒ Subnet (서브넷)1. 서브넷이란?서브넷은 하나의 네트워크를 더 작은 네트워크들로 나누는 개념이다.  2. 그렇다면 서브넷은 왜 사용할까?IP 주소의 효율적 사용큰 네트워크를 작은 네트워크로 나누어 IP 주소를 절약네트워크 성능 향상한 서브넷에서 발생한 트래픽은 다른 서브넷에 영향을 주지 않기 때문에 성능 향상보안 강화민감하나 데이터를 다루는 서브넷과 일반 사용자 서브넷을 분리하여 보안 강화확장성필요에 따라 서브넷을 추가 및 조정하여 네트워크를 확장     ❒ Subnet Mask (서브넷 마스크)1. 서브넷 마스크란?서브넷 마스크는 IP 주소..

❒ Description날짜2024.09.23 (월)레벨Medium제목Minimum Height Trees링크https://leetcode.com/problems/minimum-height-trees/description/자료구조그래프시간복잡도O(N)     ❒ 문제 분석이 문제는 트리의 리프 노드에서부터 루트로 다가가며 해결해야 한다. 여기서는 차수가 1인 리프노드를 제거하면서 루트로 다가가야 한다. 가장 낮은  차수를 제거하는 방식은 위상 정렬과 유사한 방식으로 해석할 수 있다. ※ 차수(degree) : 각 노드가 가진 서브트리의 갯수    ❒ Solution1. 리프노드를 제거하는 방법더보기더보기public List findMinHeightTrees(int n, int[][] edges) { ..

❒ Description날짜2024.09.22 (일)레벨Easy제목Balanced Binary Tree링크https://leetcode.com/problems/balanced-binary-tree/description/자료구조그래프시간 복잡도O(N) 이번 문제를 풀기 위해서는 Height-Balanced Binary Tree에 대한 이해가 필요하다.     ❒ Solutionpublic void isBalanced(TreeNode root) { return depth(root) != -1;}public int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(..

❒ Description[LeetCode#110] Balanced Binary Tree 문제를 풀면서 접하게 된 개념을 정리하자.     ❒ Height-Balanced Binary Tree1. Height-Balanced Binary Tree란?height-balanced Binary Tree는 트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하인트리를 말한다. 즉, 트리의 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 크게 나지 않도록 균형을맞춘 형태다. 이 균형 덕분에 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도를 최소화할 수 있다.  2. 주요 특징 i ) 높이 차이 제한각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이다. ii ) 탐색 ..

❒ Description날짜2024.09.22 (토)레벨Easy제목Invert Binary Tree링크https://leetcode.com/problems/invert-binary-tree/자료구조그래프알고리즘X시간 복잡도O(n) 이번 문제는 재귀구조를 연습할 수 있는 좋은 문제였다. 다양한 풀이 방법을 통해 재귀에 익숙해지자.     ❒ Solution1. 새로운 노드 생성 DFSpublic invertTree(TreeNode root) { if (root == null) return null; // 1. 새로운 노드 생성 TreeNode inverted = new TreeNod(root.val); // 2. 새로운 노드의 left, right 설정 invert..

❒ Description날짜2024.09.21 (토)레벨Medium제목Longest Univalue Path링크https://leetcode.com/problems/longest-univalue-path/submissions/1397321235/자료구조트리알고리즘X시간 복잡도O(n) 543. Diameter of Binary Tree와 굉장히 유사한 문제이다.     ❒ 문제 분석부모-노드의 value와 자식-노드의 value가 동등한지를 판단하여야 하는 문제이다. 이 문제 또한 재귀를 통해 Left, Right 자식 트리의 깊이를 파악함과 동시에 가장 긴 경로를 파악해야 한다.위 그림에서 리프노드의 1과 1은 부모노드의 값인 4와 동일하지 못하기 때문에 문제의 요구사항에 충족하지 못한다.     ❒ S..

❒ Description트랜잭션은 ACID라는 속성을 가진다. 그 중 A는 Atomicity, 원자성을 의미한다. 원자성을 보장하기 위해서commit과 rollback이 존재한다. 오늘은 트랜잭션들이 동시에 시작될 때 rollback이 발생하면 어떤 일들이벌어지는지 알아보자.     ❒ Concurrency Control : recoverability1. Unrecovarable Schedule위 그림에서 Tx2는 chul_money를 2000에서 5000으로 update를 해주었기 때문에 Rollback이 발생할경우 다시 2000으로 돌려놔야 한다. 이렇게 되면 Tx2는 더 이상 유효한 작업이 아니게 된다.따라서 Tx2에서 write 했던 chul_money를 읽은 tx1도 롤백을 해줘야 Atomac..

❒ Description레벨Easy날짜2024.09.19 (목)제목Assign Cookies링크https://leetcode.com/problems/assign-cookies/description/자료구조배열알고리즘그리디시간 복잡도O(NlogN)     ❒ 문제 분석우선 각 배열의 의미를 잘 이해해야 한다.g 배열 : i번 째 아이들를 만족시킬 수 있는 쿠키의 크기들의 집합i 배열 : 각 쿠키의 크기를 나타낸 집합예를 들어 g = {1, 2, 3}, s = {1, 1} 이라면 최대 1명의 아이만 만족할 수 있다.s[1]은 g[1]을 만족시킬 수 있다.s[2]은 g[2]을 만족시킬 수 없다.s[2]은 g[3]을 만족시킬 수 없다.     ❒ Solutionpublic int findContentChildr..