알고리즘/LeetCode
[LeetCode] #106. Construct Binary Tree from Inorder and Postorder Traversal [트리/해쉬/분할정복/파이썬/python]
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ Construct Binary Tree from Inorder and Postorder Traversal - 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 전위순회(inorder traversal)와 후위순회(postorder traversal)에 대한 개념을 아는지, 그것을 활용하여 재귀를 통해 bin..
[LeetCode/리트코드]#441: Arranging Coins[python/파이썬/이분탐색/수학]
https://leetcode.com/problems/arranging-coins/ Arranging Coins - 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+2+3...+k = k(k+1)/2 라는 공식이 있다. 이를 이용하여 이분탐색이나 수학 알고리즘으로 구현할 수 있다. 접근법 1) 이분탐색 _Binary Search 시간복잡도 O(log N) class Solution(object): def arrangeCoins(self, n): """ :typ..
[LeetCode/리트코드]#668:Kth Smallest Number in Multiplication Table[파이썬/python/이분탐색/Binary Search]
https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ Kth Smallest Number in Multiplication Table - 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 브루트포스(완전탐색)이나 힙을 이용하여 구현하면 시간초과가 뜬다. 처음에 힙을 이용하여 구현했다가 시간초과를 받았다. 각 n줄에 대하여 가장 작은 사용안한 원소를 힙에서 pop하는 알고리즘 시간초과 코드..
[LeetCode/리트코드]#368. Largest Divisible Subset[파이썬/python/수학]
https://leetcode.com/problems/largest-divisible-subset/ class Solution: def largestDivisibleSubset(self, nums: List[int]) -> List[int]: ans=[] max_ind=0 divcnt=[0 for i in range(len(nums))] prev=[-1 for i in range(len(nums))] nums.sort() idx=-1 for i in range(len(nums)): for j in range(i): if nums[i]%nums[j]==0: if divcnt[i] < divcnt[j]+1 : divcnt[i]=divcnt[j]+1 prev[i]=j if divcnt[max_ind] < di..
[LeetCode/리트코드]#1286. Iterator for Combination[파이썬/python/문자열/String]
https://leetcode.com/problems/iterator-for-combination/ class CombinationIterator(object): def __init__(self, characters, combinationLength): """ :type characters: str :type combinationLength: int """ self.len = len(characters) self.characters = characters self.pointers = [i for i in range(combinationLength)] self.pointers[-1] -= 1 self.thres = [i for i in range(self.len -len(self.pointers), sel..
[LeetCode/리트코드]#739:Daily Temperatures [파이썬/python/배열/array]
https://leetcode.com/problems/daily-temperatures/ 온도 list를 받으면 각 날에 대해 - 현재날짜보다 다음날짜가 따뜻한 날짜의 개수(number of days)를 구하는 것이다. 브루트포스 문제로 완전탐색을 하면된다. 각 온도의 날짜를 모두 돌면 O(N^2)의 시간복잡도다. 비효율적인 완전탐색보다 좀 더 빠르게 짤 수 없을까? 배열을 사용하여 구현해보자. N(온도길이)만큼 iterate하면 시간복잡도는 O(N)이다. 공간복잡도 또한 O(N)이다. class Solution(object): def dailyTemperatures(self, temperatures): """ :type temperatures: List[int] :rtype: List[int] """ ..
[LeetCode/리트코드] #203. Remove Linked List Elements [큐/queue/python/파이썬]
https://leetcode.com/problems/remove-linked-list-elements/ Remove Linked List Elements - 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 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution..
[LeetCode/리트코드] #1413. Minimum Value to Get Positive Step by Step Sum [Prefix Sum/파이썬/python]
https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/ Minimum Value to Get Positive Step by Step Sum - 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 class Solution: def minStartValue(self, nums: List[int]) -> int: start=1 while True: total = start is_valid..
[LeetCode/리트코드] #1178. Number of Valid Words for Each Puzzle[파이썬(python)/Bitmask/비트마스크]
https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/ Number of Valid Words for Each Puzzle - 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 처음에는 문자열 문제인 줄 알고 쉬운 문제라고 생각하고 풀었으나 응 바로 시간초과 ^__^ 시간초과 난 코드 class Solution: def findNumOfValidWords(self, words: List[str], ..
[LeetCode/리트코드] #96. Unique Binary Search Trees[파이썬(python)/C++/BST]
https://leetcode.com/problems/unique-binary-search-trees/ Unique Binary Search Trees - 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 BST(Binary Search Tree)는 root노드의 왼쪽으로는 더 작은 값, 오른쪽으로는 더 큰 값을 가지는 트리다. 그래서 탐색 순회하기 효율적인 자료구조를 가진다. 노드의 개수를 입력으로 받았을 때 만들 수 있는 BST의 개수를 출력으로 하면 된다. 점..