본문 바로가기
반응형

분류 전체보기714

501 : Find Mode in Binary Search Tree ( leetcode / java ) *해결 과정 이진탐색 트리라는 것을 친절하게 설명하고 있습니다. 그것보다도, 중복된 요소를 찾고 list로 반환하는 것이 더 중요해보입니다. Integer만을 다루는 Map의 형태이며 중복을 찾아야 하기 때문에 모든 요소 값에 따라서 등장할 때마다 +1씩 하도록 했습니다. 그리고 처음부터 순회하면서 value값이 최대로 큰 경우를 고르고 key값을 list에 넣어서 반환합니다. import java.util.*; class Solution { Map map = new HashMap(); public int[] findMode(TreeNode root) { if(root==null) return new int[]{}; DFS(root); int max = Collections.max(map.values().. 2020. 11. 2.
Map에서 Key, Value 다루기 알고리즘 문제를 풀다보면 map으로 해결해야 하는 상황이 많습니다. 또한 map을 적절히 이용해 문제가 원하는 key값과 value값을 꺼낼 수 있어야 합니다. 빠르고 쉽게 값을 뽑아내는 방법을 알아보겠습니다. 다음의 조건이 주어질 때 어떤 방식을 사용하는 것이 효율적일까요? 개인적으로 iterator를 순회하는 것보다 for문으로 조회하는 것을 선호합니다. Map 기준 *변형 내용 1. Map의 요소들을 순회하는 방법은? ( 1. key 순회 2.value 순회 3. key , value 동시 순회) 2. Map의 key 값, value 값 중 최대 값을 뽑는 방법은? 3. Map의 value값 중 최대 값의 key값을 뽑는 방법은? ( + 중복일 경우도 포함) 1번 import java.util.Ha.. 2020. 11. 2.
MVC vs MVP vs MVVM Controller에 Input이 들어온다. View와 Controller는 MVC 구조에서 설계의 상단에 위치한다. Model은 그 아래 위치하며, 따라서 View는 Controller에 대해 알고 있고 Controller는 Model에 대해 알고 있다. View는 Model에 직접 접근이 가능하다. 단점 : 모든 Model을 View에 노출시키는 것은 어플리케이션의 복잡성에 따라 보안문제, 비용문제 등이 발생한다. 데이터베이스에 있는 모든 Model들은 자신들에 맞는 Controller를 호출하는데, 어플리케이션이 더 복잡해지고 많은 연관된 모델을 가지는 시스템으로 확장된다. 사용되는 Controllers의 숫자는 엄청 커질 것이다. 따라서 탐색 속도가 느려진다. Ruby on Rails, Apple.. 2020. 11. 2.
Framework vs Library vs API 라이브러리는 다양한 함수를 제공하는 코드들을 의미한다. 반복적인 작업을 처리하기 위해서 자신만의 코드를 호출할 수 있다. 예를 들어, math 라이브러리는 삼각법이나 로그 함수같은 반복적인 수학적 기능을 제공한다. 프로그래밍 언어들(java, c , python)은 데이터 가공, 그래프 조작, 문자열 파싱 등의 작업을 위한 라이브러리들을 가지고 있다. 라이브러리가 있다면, 모든 복잡한 기능을 스스로 만들어야 하는 문제를 해결해 줄 수 있다. Application Programming Interface의 축약어이다. Interface는 상호작용, 중개라는 사전적 해석처럼 서로 다른 응용프로그램에서 사용할 수 있도록 제어할 수 있도록 만들어진 것이다. 프로그래머가 쉽게 접근할 수 있으며 라이브러리의 "표면".. 2020. 11. 1.
2504 : 괄호의 값 ( 백준 / java ) *해결 과정 괄호를 가지고 계산하는 것은 보통 stack을 이용하면 됩니다. 이 문제도 마찬가지로 stack을 이용합니다. 이전의 stack문제와 다른 것은, '(' 에 대한 ')'의 위치 index를 저장하고 재귀적으로 해결했지만 이번에는 그런 방식으로 하면 시간초과가 난다는 것입니다. 그래서 문자열을 하나씩 탐색하면서 Nlog(N)에 해결하도록 하였습니다. (N은 문자열 길이이고, 문자열을 하나씩 살펴보며 검사하지만 괄호 안에 다른 내용이 있을 경우 다시 while문 으로 모두 stack.pop()하는 과정이 있으므로 최악의 경우 N을 곱했습니다.) 특히 '('는 0으로 치환, '['은 1로 치환하여 stack에 저장하였으며 어차피 계산과정에서 0과 1을 만날 일이 없기 때문에 괄호라고 식별 가능합니.. 2020. 10. 30.
572 : Subtree of Another Tree( leetcode / java ) *해결 과정 t라는 트리가 s라는 트리에 포함되는지 확인하는 문제입니다. 간단하게 생각하면 각 root의 val값이 같을 때, 재귀적으로 비교해주면 됩니다. 하지만 예외 상황이 있네요. 아래의 경우입니다. 도대체 왜 val값을 독립적으로 만들지 않고 중복되게 만든 것이야!! 결국 우리는 "모든 노드를 순회하면서" val값이 같은 경우 해당 경우가 있는지 없는지 확인해야 합니다. 조건을 세워 봅시다. 초기조건 : 둘다 null이면 true입니다. 같다는 의미는 둘 다 leaf노드가 같다는 의미입니다. 혹시 한쪽만 null이면 false입니다. 당연히 s,t중 한 쪽만 특정 자손을 가지면 다르겠지요. 또한 val값이 서로 다르면 false입니다. 재귀 조건 + 반환조건 : s.left, t.left 와 s... 2020. 10. 30.
543 : Diameter of Binary Tree ( leetcode / java ) *해결 과정 리스트에서야 지름 구하는 것을 풀었지 tree에서 지름구하는 문제는 처음입니다. 처음에 root에서 왼쪽 자식의 맨 아래 자손 깊이, 오른쪽 자식의 맨 아래 자손의 깊이를 더해서 출력했는데 틀렸씁니다. 왜냐하면 꼭 루트에서 이어진 길이가 지름이라는 법이 없기 때문입니다. 그래서 각 노드를 모두 root라고 생각하고 순회하면서 비교해야 합니다. 리스트, 트리의 지름 = 가장 멀리 떨어져 있는 두 노드의 거리 빨간점을 기준으로 생각해봅시다. 해당 노드에서 지름은 어떻게 구할까요? 다음 2가지를 생각해 보시길 바랍니다. 1. 어떻게 해당 노드에서 지름의 길이를 구할 것인가 ( 종료 조건, 재귀로 계산하는 과정, return) 1-1. 무엇을 return 할 것인가? ( 최대 결과값을 반환 할 것인.. 2020. 10. 30.
563 : Binary Tree Tilt ( leetcode / java ) *해결과정 불쌍한 문제입니다. ㅜㅜ 비추수가 압도적으로 많습니다. 일반적인 tree의 문제가 아니라 그런 것 같습니다. 최근에 풀었던 파x 기업의 3번문제와 비슷합니다. postOrder 형식의 처리가 필요합니다. 즉, leaft쪽으로 먼저 이동해 root의 왼쪽 자식과 오른쪽 자식의 값을 계산하여 계속 부모쪽으로 올라오면서 최신화를 시켜주면 됩니다. 우리는 Tilt의 값을 찾으면 되기 때문에 굳이 TreeNode의 root값들을 최신화 시켜 줄 필요는 없습니다. class Solution { int totalTilt=0; public int findTilt(TreeNode root) { valueSum(root); return totalTilt; } public int valueSum(TreeNode .. 2020. 10. 30.
235 : Lowest Common Ancestor of a Binary Search Tree ( leetcode / java ) * 해결과정 제목에 이진탐색 트리라고 써있습니다. 이를 적극적으로 활용합니다! (하지만 저는 또 그냥 지나쳤습니다.. ㅜㅜ) 또한 최소 공통 조상에 대한 문제이기도 합니다. 하지만 걱정하지 않아도 되는 것은 이진탐색 트리이기 때문에, 또한 p,q가 동시에 주어졌기 때문에 간단하게 해결 할 수 있습니다. 각 해당 노드의 값의 대소비교를 통해 해결합니다. class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int parentVal = root.val; int pVal = p.val; int qVal = q.val; if(pVal>parentVal && qVal>parentVal) return.. 2020. 10. 30.
반응형

티스토리툴바