개인 공부/알고리즘
-
스레드 이진 트리 (Threaded Binary Tree)개인 공부/알고리즘 2021. 10. 10. 01:47
* 참고: https://youtu.be/AndqtbiTfe8 1. 기존 이진 트리의 문제점 왼쪽 자식, 값, 오른쪽 자식을 저장하는 일반적인 이진 트리의 경우 대다수의 포인터(n+1)들은 null을 가리키고, 이는 메모리의 낭비를 일으킨다. 이런 이진 트리의 순행하기 위해서 스택 또는 큐가 필요한데, 이 역시 많은 저장공간을 필요로 하게 된다. 이를 해결하기 위해 우리는 스레드 이진 트리를 사용한다. 2. 스레드 이진 트리의 특징 스레드 이진 트리는 널 포인터 대신 의미 있는 정보들을 저장한다. 운행을 위해 스택 또는 큐를 사용하지 않는다. 이때 의미 있는 정보들이란 중순위 선행/계승 정보를 가리킨다. 왼쪽 null 포인터는 선행 노드를 가리키고 오른쪽 null 포인터는 계승 노드를 가리키도록 한다. ..
-
[GeekforGeeks] Key Pair개인 공부/알고리즘 2021. 5. 30. 19:23
Key Pair 문제 n개의 양의 정수값을 가지는 배열에서 두 수의 합이 정확히 특정 숫자 x가 되는 원소가 존재하는지 여부를 반환하여라. class Solution { boolean hasArrayTwoCandidates(int arr[], int n, int x) { // code here HashMap pairs = new HashMap(); for (int i = 0; i < arr.length; i++) { if (pairs.containsValue(arr[i])) return true; else pairs.put(arr[i], x - arr[i]); } return false; } }이제 이 문제는 아예 푸는 법을 외워버렸다...😅
-
[LeetCode] Climbing Stairs개인 공부/알고리즘 2021. 5. 18. 01:56
Climbing Stairs 처음으로 직접 맞힌 동적 프로그래밍 문제...!!!!!!!😭😂 class Solution { public int climbStairs(int n) { int [] counts = new int[n+1]; counts[1] = 1; if (n > 1) counts[2] = 2; for (int i = 3; i 1 2 -> 2 3 -> 1+1+1 / 1+2 / 2+1 4 -> 1+1+1+1 / 1+2+1 / 1+1+2 / 2+1+1 / 2+2 ... 그리고 나열한 것들을 뚫어지게 쳐다봤다..^-^.. 1+1+..+1 제외하면 바로 전이랑 관련이 있나 생각해봤다. (답은 아니지만 암튼 그렇게도 생각해봤다.) 내가 나열한 목록은 순서 없이 마구잡이로 나열된 것이라는 생각이 들었다. ..
-
[LeetCode] Flip Equivalent Binary Trees개인 공부/알고리즘 2021. 5. 16. 22:11
Flip Equivalent 처음 코드 class Solution { public boolean flipEquiv(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) return true; if (root1.val != root2.val || root1.left.val != root2.left.val && root1.left.val != root2.right.val || root1.right != root2.left.val && root1.right.val != root2.right.val) return false; boolean equiv1, equiv2; if (root1.left.val == root2.left.val) { e..
-
[LeetCode] Valid Anagram개인 공부/알고리즘 2021. 5. 8. 07:30
Valid Anagram My Solution : class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) return false; char [] sArray = s.toCharArray(); char [] tArray = t.toCharArray(); Arrays.sort(sArray); Arrays.sort(tArray); if (Arrays.equals(sArray, tArray)) return true; else return false; } } 마지막에 그냥 return Arrays.equals(sArray, tArray)라고 작성하면 되는 거였다..ㅠㅠ .sort() 메소드 사용할 경우..
-
[Leetcode] Valid Parentheses개인 공부/알고리즘 2021. 4. 25. 23:20
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. import java.util.Stack; import java.util.Scanner; public class Solution { public boolean isValid(String s) { Stack stack = new Stack(); ch..