반응형 알고리즘211 [알고리즘] Convert Sorted Array to Binary Search Tree 포인트 재귀적으로 오름차순 정렬로 bst를 만드는 알고리즘입니다. 코드 전체를 보면, 이분 탐색과도 비슷한 형태를 띄고 있습니다. 이점을 참고하시면 더욱 좋을 것 같습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: return self.bst(0, len(nums) - 1, nums) def bst(self,left:int, right:int, nums:List[int]) -> TreeNode: if left>right: # 이분 탐색 처럼 움직인다. return mid = left+(right-left)//2 # 다른 언어일 경우, 오버 플로우가 .. 2021. 7. 26. [알고리즘] Binary Tree Pruning 포인트 Pruning 가지치기를 뜻하면 백트랙킹에서 사용하는 단어 입니다. 이 문제에서는 0을 가지고 있는 것을 왼쪽 노드와 오른쪽 노드가 None 인 것을 찾는 문제 입니다. 재귀적인 방법으로 탐색하여 처리하는 문제 입니다. 트리를 탐색하는 방법 중 후위 탐색과 비슷한 모양입니다. 참고하시면 좋을 것 같습니다. https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C 트리 순회 - 위키백과, 우리 모두의 백과사전 전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 ko.wikipedia.or.. 2021. 7. 24. [알고리즘] Lowest Common Ancestor of a Binary Search Tree 포인트 LCA 공통 조상 문제를 이진 탐색 문제에서 어떻게 해결할 수 있는가? 를 물어보는 문제 입니다. 반복문과 재귀 2가지 방향으로 풀이를 할 수 있습니다. 개인적으로 반복문의 형태가 이해하기 편하다고 생각합니다. 기준 노드들 전부보다 크다면 오른쪽 노드를 다시 확인 전부 작다면 왼쪽 노드를 다시 확인 그렇지 않을 경우 그 노드가 최소 공통의 조상 노드가 됩니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python # Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def lowestCom.. 2021. 7. 19. [알고리즘] 4Sum 2021.07.15 - [알고리즘] - [알고리즘] Valid Triangle Number [알고리즘] Valid Triangle Number 포인트 규칙을 만족하기 위한 세 수 갯수를 세는 문제 해결 입니다. 일반적인 해결 방법은 for loop 를 3번만 한다면, 해결할 수 있는 조건 입니다. 하지만, 이 경우 시간 초과를 경험할 수 있습니다 keelim.tistory.com 포인트 만약 1년 전에 저였다면, 4중 for loop 를 돌고 틀려놓고 왜 틀렸을까? 라는 의문을 던졌을 텐데 지금 단계는 "아 무조건 4중 for loop 는 아닌 것 같은데"로 생각이 전환된 느낌입니다. 저는 그래서 이를 쪼개서 2중 포문 + 투 포인터 전략으로 해결하였습니다. 이와 같은 문제 접근 방법인 is Valid .. 2021. 7. 16. 이전 1 2 3 4 5 6 ··· 53 다음 반응형