JW's dev blog

Recursion과 Dynamic Programming에 대해 간략하게 정리하고 Leetcode 문제를 풀어보자. Recursive solution은 한 문제를 여러 서브 문제로 쪼개 결과를 합치는 방법이다. 이러한 Recursive solution에는 크게 세 가지의 접근 방식이 있다. 바로 Top-down approach, bottom-up approach, 그리고 half-and-half approach다. bottom-up 은 f(0) -> f(1) -> f(2)->...->f(n) 이런 식이고, 탑다운은 반대로 생각하면 된다. 하프앤하프의 대표적인 예로는 binary search와 merge sort가 있다. Recursion 우선 Recursion은 공간복잡도가 비효율적이다. 모든 Recurs..

과목을 수강할 때 선수과목을 먼저 수강하면서 차례대로 들어야하는 문제이다. 문제의 자세한 내용은 아래에서 확인할 수 있다. https://leetcode.com/problems/course-schedule-ii/ Course Schedule II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제를 읽고 내가 생각한 것은 1. directed graph 라는것 2. bfs로 구현하면 되지 않을까였다. 그렇다면 가장 먼저 들을 과목이 root 노드가 되어야하는..

앞서 두 글에서 트리에 대해 알아보았다. [자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등) 트리 (Tree)란? 트리는 노드로 구성된 자료구조이다. - 트리는 루트노드(root node)를 가진다. - 루트노드는 0개 이상의 자식노드(child nodes)를 가진다. - 각 자식노드 또한 0개 이상의 자식노드를 가진 jwdevv.tistory.com [자료구조] 트리 (Tree) - 이진 트리 순회 (Binary Tree Traversal) | 트라이 (Trie, Prefix Trees) 이전글 [자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등) 트리 (Tree)란? 트리는 노드로 구성된 자료구조이다. - 트리는 루트노드(root node)를 가진다. - 루트노드는 ..

이전글 [자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등) 트리 (Tree)란? 트리는 노드로 구성된 자료구조이다. - 트리는 루트노드(root node)를 가진다. - 루트노드는 0개 이상의 자식노드(child nodes)를 가진다. - 각 자식노드 또한 0개 이상의 자식노드를 가진 jwdevv.tistory.com 이진 트리 순회방법에는 세가지가 있다. in-order, pre-oder, post-order 이다. In-Order Traversal (중위순회) in-order traversal은 left -> current -> right 노드 순서로 순회하는 방법이다. def inOrderTraversal(node): if node != None: inOrderTraversal(n..

오늘은 Min Stack을 구현하는 문제를 풀어보자. 문제는 아래 leetcode에서 확인할 수 있다. https://leetcode.com/problems/min-stack/ Min Stack - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Min Stack이란 push, pop, top, getMin function을 가지는 스택이다. 여기서 전제 조건은 모든 function은 시간 복잡도가 O(1)이어야 한다. pop과 top은 기존 스택처럼 구현하면 된..

오늘은 Linked List 문제를 풀어보았다. 단방향 연결 리스트의 중간에 있는 노드 하나가 주어지면 그 노드를 삭제하는 문제다. 이 때 head에는 접근할 수 없고, 각 노드는 각기 다른 정수를 value로 가진다. 여기서 중간 노드라는 이야기는 정확하게 정중앙에 있는 노드라는 뜻이 아니라 맨 첫번째나 맨 끝이 아닌 노드, 즉 그 중간에 있는 노드들 중 하나라는 뜻이다. 문제는 여기서 확인할 수 있다. https://leetcode.com/problems/delete-node-in-a-linked-list/ Delete Node in a Linked List - LeetCode Level up your coding skills and quickly land a job. This is the best ..

이전에 정렬 및 탐색을 공부할 때 아나그램끼리 묶는 문제를 풀었다. [알고리즘, Python] 아나그램(Anagram) 묶기 오늘 풀어볼 문제는 Anagram끼리 묶는 문제다. 여기서 Anagram이란 단어의 문자열은 같지만 순서는 다른 것들을 말한다. 예를 들면 "eat"과 "tea"는 모두 a, e, t 로 이루어진 단어지만 순서는 다르다. Leet jwdevv.tistory.com 이번에는 단순히 두 문자열이 주어지고 둘이 아나그램인지 확인하는 문제를 풀 것이다. * leecode에서 문제 보기 https://leetcode.com/problems/valid-anagram/ Valid Anagram - LeetCode Level up your coding skills and quickly land ..

문제는 leecode에서 확인할 수 있다. https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제를 풀기 전 기존에 정렬 배열에서 어떻게 탐색하는지 생각해보자. 탐색이므로 직관적으로 binary search를 사용해야겠다는 생각이 든다. 예를 들어 [1, 2, 4, 5, 7, 8, 9] 라는 배..

오늘 풀어볼 문제는 Anagram끼리 묶는 문제다. 여기서 Anagram이란 단어의 문자열은 같지만 순서는 다른 것들을 말한다. 예를 들면 "eat"과 "tea"는 모두 a, e, t 로 이루어진 단어지만 순서는 다르다. Leetcode에서 문제보기 솔루션 1. 내가 처음 생각해낸 코드는 아래와 같았다. 우선 모든 단어를 돌며 정렬한 후 anagram이 존재하면 그 array에 넣어주고 없으면 result에 새로운 배열을 추가한다. 즉 ["eat", "tea", "hi", "hello", "ate"]가 있다고 했을 때 "eat"를 정렬하면 "aet"이다. anagrams에 존재하지 않는다. 추가해준다. anagrams = ["aet"] result = [["eat"]] "tea"를 정렬하면 "aet"다...

이미 정렬된 두 개의 배열을 병합하는 문제를 풀어보자. Leetcode에서 문제보기 Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] 문제에서는 정렬된 두 배열 nums1, nums2 그리고 각 배열의 길이인 m과 n이 주어진다. nums1의 길이는 m+n이다. 이 문제는 기존 병합 정렬 코드보다 더 간단하다. (병합 정렬에 대해 알아보기 : https://jwdevv.tistory.com/3) [알고리즘, Python] 정렬 1 - 병합 정렬(Merge Sort) 정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리..