본문 바로가기

old/Algorithm Solving

(58)

LeetCode 112. Path Sum 자바 문제 풀이 문제 LeetCode - The World's Leading Online Programming Learning Platform 문제 해결 방법 이 문제의 목적은, 주어진 이진 트리에서 루트부터 잎 노드까지의 경로 중 합이 주어진 targetSum과 같은 경로가 있는지 확인하는 것입니다. 그러므로, 이 코드는 주어진 이진 트리에서 재귀적으로 경로를 탐색하고, 경로 합이 targetSum과 같은지 확인합니다. 알고리즘 재귀 함수 호출 (Recursion): hasPathSum 함수는 재귀적으로 호출됩니다. 이 함수는 현재 노드의 값을 targetSum에서 빼고, 이 값을 새로운 targetSum으로 사용합니다. 기본 케이스 (Base Case): 재귀 호출이 시작될 때, 현재 노드가 null인지 확인하여 트..

LeetCode 2413. Smallest Even Multiple 자바 문제 풀이 문제 Smallest Even Multiple - LeetCode 문제 해결 방법 multiple of 2라는 뜻은 숫자가 짝수여야 한다는 뜻이다. multiple of n라는 뜻은 숫자가 n의 배수여야 한다는 뜻이다. 이 문제는 n의 배수중에 가장 작은 짝수를 찾는 문제이다. 처음에는 n을 반복해서 증가시키고, 그중 짝수면 리턴하는 알고리즘을 짰었다. 하지만 그러고 깨달았다. 두번째 n의 배수는 언제나 짝수일수밖에 없다. 그러므로 가장 효율적인 알고리즘은 아래와 같다 n이 짝수인지 확인한다. n이 짝수라면 n을 리턴한다. n이 짝수가 아니라면 다음배수는 언제나 짝수이다. 그러므로 n*2를 리턴한다. Github Link https://github.com/eunhanlee/LeetCode_2413_Sma..

LeetCode 75. Sort Colors 자바 문제 풀이 문제 Sort Colors - LeetCode 문제 해결 방법 정렬을 하는데 함수(메서드)를 쓰지 말라는 조건이 붙었으므로, 정렬알고리즘을 구현할수 있는지 물어보는 문제입니다. input이 0,1,2뿐이므로, 이를 이용한 로직 알고리즘으로 푸는 것이 가능합니다. 알고리즘 모든 엘레멘트를 순회하며, 0,1,2의 개수를 확인합니다 각 개수만큼 0,1,2순서대로 어레이에 넣습니다. Follow up에서 원하는 one-pass algorithm은 네덜란드 국기 알고리즘을 알고 있느냐고 묻는것이며, 이 알고리즘은 0,1를 정렬하는데 특화된 알고리즘 입니다. 또는 퀵정렬을 구현할수도 있습니다. 참고 네덜란드 국기(Dutch National Flag) 알고리즘이란 퀵정렬이란 Github Link https://git..

LeetCode 1672. Richest Customer Wealth 자바 문제 풀이 문제 Richest Customer Wealth - LeetCode 문제 해결 방법 2D어레이를 다루어서 값을 모두 더하고, 그를 이용해서 최적화를 할수 있는가 물어보는 문제이다. 처음에는 간단하게 다 더한 값을 어레이에 저장하고, 그 어레이를 지나며 최대값을 찾는 방식으로 답을 구하였는데, 최적화를 잘하면 굳이 어레이에 값을 저장할 필요가 없이 바로 최대값을 찾으면 된다. 일단 다 짠다음에서야 최적화가 가능하다는것을 깨달았는데, 바로 좋은 알고리즘을 짤수있도록 많이 문제를 풀어봐야 한다. 알고리즘 첫번째 반복문에서 각 어레이를 가져온다 두번쨰 반복문에서 각 어레이의 값을 모두 더한다 두번째 반복문이 끝나면 모두 더한값을 비교하여, 높은 수일 경우 저장한다 저장한 값을 리턴한다. Github Link h..

GFG Count the Substrings 자바 문제 풀이 문제 Problem_Link 문제해결방법 조건: 대문자와 소문자의 개수가 같은 substring 특정 substring의 시작점과 끝점의 대소문자 차이가 같다면, 그 substring은 조건에 맞는 substring 이라 볼수 있다. 예제: “AbaBBa” 위 예제의 substring의 총 개수는 21개 이며, 조건에 맞는 substring은 7개이다. 대소문자 차이를 구하기 위해 대문자이면 +1을, 소문자이면 -1을 사용한다. 시작점은 대소문자 차이가 없으므로 0이다. index 없음 0 1 2 3 4 5 element 시작점 A b a B B a 대소문자 차이 0 1 0 -1 0 1 0 같은 대소문자 차이를 가지고 있는 사이의 substring은 조건에 맞는 substring이다. substring ..

LeetCode 236. Lowest Common Ancestor of a Binary Tree 자바 문제 풀이 문제 Lowest Common Ancestor of a Binary Tree - LeetCode 문제 해결 방법 최소공통 조상LCA를 알고 있느냐고 묻고, 이를 구현할수 있느냐고 묻는 문제입니다. LCA의 전처리 과정은 이 문제에서는 사용할수 없습니다. Tree Node를 수정할수 없기떄문입니다. 그러므로, 보통 LCA알고리즘은 목표로하는 두 노드에서 부모로 올라가며 비교하는 방식이지만, 이 문제의 경우 root에서 하나씩 아래로 내려가며, p나 q가 현재 노드와 같은가 비교하여 구합니다. 참고 최소 공통 조상, LCA(Lowest Common Ancestor)이란 Github Link https://github.com/eunhanlee/LeetCode_236_LowestCommonAncestorofaB..

LeetCode 2235. Add Two Integers 자바 문제 풀이 문제 Add Two Integers - LeetCode 문제 해결 방법 단순하게 연산을 해서 리턴하는 능력을 시험하는 문제입니다. 가로()는 자바 우선순위에 따라서 사용할 필요가 없습니다. 참고 복잡한 표현식의 연산자 그룹화: 자바 연산자 우선순위 Github Link https://github.com/eunhanlee/LeetCode_2235_AddTwoIntegers_Solution.git 시간복잡도: O(1), 공간복잡도: O(1) class Solution { /** * Returns the sum of two integers. * * @param num1 The first integer. * @param num2 The second integer. * @return The sum of num1 ..

LeetCode 1512. Number of Good Pairs 자바 문제 풀이 문제 Number of Good Pairs - LeetCode 문제 해결 방법 반복문안에 또다른 반복문(for)과 다중조건(if, &&연산자)을 잘 잡을수 있는지 묻는 문제 입니다. Github Link https://github.com/eunhanlee/LeetCode_1512_NumberofGoodPairs_Solution.git 시간복잡도: O(n^2), 공간복잡도: O(k) class Solution { /** * 주어진 배열에서 동일한 쌍의 개수를 계산합니다. * * @param nums 정수 배열입니다. * @return 배열에서 동일한 쌍의 개수입니다. */ public int numIdenticalPairs(int[] nums) { int counter = 0; // 동일한 쌍의 개수를 세..

이전 1 2 3 4 ··· 8 다음

티스토리툴바