본문 바로가기

🧩 Algorithm19

LeetCode : 133. Clone Graph 문제 링크 문제 먼저 읽기 연결된 방향이 없는 그래프에서 노드의 참조가 주어집니다. 깊은 복사를 한 그래프를 반환하세요. 어떻게 풀까? 생각 이웃을 순회하면서 재귀로 해결하는 것을 시도해보았습니다. 수도코드 class Solution { public Node cloneGraph(Node node) { ArrayList neighbors = new ArrayList(); boolean[] visit = new boolean[101]; for (int i=0; i 2023. 9. 15.
LeetCode : 211. Design Add and Search Words Data Structure 문제 링크 문제 먼저 읽기 새 단어를 추가하거나 추가한 단어와 일치하는 문자열을 찾을 수 있는 데이터 구조를 구현해봅시다. WordDictionary() 객체를 초기화합니다. void addWord(word) 데이터 구조에 단어를 추가하며, 나중에 일치시킬 수 있습니다. void search(word) 데이터 구조에 단어와 일치하는 문자열이 있으면 참을 반환하고 그렇지 않으면 거짓을 반환합니다. 단어는 점 '.'을 포함할 수 있으며, 여기서 점은 어떤 문자와도 일치할 수 있습니다. 어떻게 풀까? 생각 Trie 를 다시한번 구현해봅시다. 어제 풀었던 문제라 생각보다 바로 수도코드를 작성할 수 있었습니다. . 이 나오는 경우에는 모든 문자를 검색할 수 있도록 합니다. 수도코드 class WordDiction.. 2023. 9. 12.
LeetCode : 208. Implement Trie (Prefix Tree) 문제 링크 문제 먼저 읽기 Trie 를 구현하세요 Trie() trie를 초기화합니다. void insert(String word) 를 insert 합니다. boolean search(String word) word가 있으면 true, 없으면 false를 반환합니다. boolean startsWith(String prefix) 이미 존재하는 단어중에 prefix로 시작하는 단어가 있으면 true, 아니면 false를 반환합니다. Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, .. 2023. 9. 11.
LeetCode : 230. Kth Smallest Element in a BST 문제 링크 문제 먼저 읽기 이진 검색 트리의 루트와 정수 k가 주어졌습니다. 트리에 있는 모든 노드의 값 중 K번째 가장 작은 값(1-indexed)을 반환합니다. 어떻게 풀까? 생각 root로부터 맨 왼쪽에 위치한 값이 제일 작은 값입니다. 거기서부터 시작해서 이전 노드, 오른쪽 노드 순서대로 탐색할 수 있는 재귀함수를 만듭니다. 수도코드 class Solution { int count = 0; int result = 0; public int kthSmallest(TreeNode root, int k) { count = k; search(root); return result; } public void search(TreeNode node) { if (node == null) return ; search.. 2023. 9. 8.
LeetCode : 530. Minimum Absolute Difference in BST 문제 링크 문제 먼저 읽기 이진 검색 트리(BST)의 루트가 주어졌을 때, 트리에 있는 서로 다른 두 노드의 값 사이의 최소 차이 절대값을 반환합니다. Input: root = [1,0,48,null,null,12,49] Output: 1 어떻게 풀까? 생각 주의! 처음에 문제를 잘못읽었었습니다. 역시 사람의 언어를 가장 잘해야 합니다 🥲 트리는 정렬 규칙상 인접 노드가 가장 그 차이가 적습니다. 그래서 인접하는 노드끼리 비교하면 안될까요? 재귀를 통해 BST 를 구현해봅시다. 수도코드 class Solution { TreeNode prev = null; int min = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { search.. 2023. 9. 8.
LeetCode : 148. Sort List 문제 링크 문제 먼저 읽기 linkedlist의 head인 ListNode가 하나 주어집니다. 이 리스트를 오름차순으로 정렬하고 head를 반환합니다. 시간복잡도 O(nlogN), 공간복잡도 O(1)의 답변이 있는 모양입니다 🫠 Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)? 어떻게 풀까? 생각 처음 문제를 읽고 좀 당황했습니다. linked list를 정렬을 다시 해본적이 없었기 때문입니다. 가장 먼저 든 생각은 새로운 LinkedList를 만들어서 이전 리스트를 탐색함과 동시에 새로운 리스트에 값을 넣어주는 것입니다. 이 경우 시간복잡도는 O(n^2)이 될 것으로 예상됩니다. 새로운 리스트에 값을.. 2023. 9. 5.
해시테이블 Hash table 해시테이블이란? https://en.wikipedia.org/wiki/Hash_table HashMap이라고도 알려진 해시 테이블(HashTable)은 키(Key)를 값(Value)로 매핑하는 추상 데이터 유형입니다. 내부적으로 연관 배열(associative array)나 딕셔너리(dictionary)을 사용하여 데이터를 저장합니다. 각 키Key에 해시 함수를 사용하여 해시코드라고도 하는 인덱스(index)를 생성하고 이 index 위치에 값(Value)가 저장됩니다. colors = { "Red" : "#FF0000", "Green" : "#00FF00", "Blue" : "#0000FF", "White" : "#FFFFFF", "Black" : "#000000", "Yellow" : "#FFFF00.. 2023. 9. 5.
LeetCode : 383. Ransom Note 문제 링크 문제 먼저 읽기 두 문자열 ransomNote와 magazine이 주어졌을 때, magazine의 문자를 사용하여 ransomNote를 구성할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다. magazine 문자는 ransomNote에서 한 번만 사용할 수 있습니다. Input: ransomNote = "aa", magazine = "ab" Output: false 어떻게 풀까? 생각 HashMap을 사용해서 magazine 의 문자 개수를 더하고하고, ransomNote 문자를 순회하면서 HashMap에 저장된 문자 개수를 차감하여 magaziine의 모든 문자들로 ransomNote를 이룰 수 있는 지 확인해본다. 이 방법으로 했을 때 O(2N)의 시간 복잡도가 들 것.. 2023. 9. 1.

티스토리툴바