JW's dev blog

트리 (Tree)란? 트리는 노드로 구성된 자료구조이다. - 트리는 루트노드(root node)를 가진다. - 루트노드는 0개 이상의 자식노드(child nodes)를 가진다. - 각 자식노드 또한 0개 이상의 자식노드를 가진다. - 트리는 cycle을 가질 수 없다. - 노드는 특정한 순서로 있을수도 없을수도 있다. - 노드는 어떤 데이터 타입도 값으로 가질 수 있다. - 노드는 부모 노드로 가는 링크를 가지고 있을수도 없을수도 있다. Node 예시 class Node: def __init__(self, data): self.data = data self.children = [] Tree 예시 class Tree: def __init__(self): self.root = None 트리의 타입 - 이진 ..

https://jwdevv.tistory.com/3 [알고리즘, Python] 정렬(sorting) - 병합 정렬(Merge Sort) 정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리 측면에서는 공간 복잡도 O(1)로 좋지만, 시간 복잡도는 O(n^ jwdevv.tistory.com 이전 글과 동일한 '배열을 정렬'하는 문제를 퀵정렬로 구현해보자. 퀵정렬은 랜덤한 요소를 피봇(pivot)으로 정해서 피봇값보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 정렬하는 방법이다. 평균 시간복잡도는 O(n log(n)) 이지만 피봇값을 어떻게 정하냐에 따라 최악의 경우에는 시간복잡도가 O(n^2)가 될 수도 있다. ..

정렬은 크게 다섯가지로 나눌 수 있다: 버블정렬, 선택정렬, 병합정렬, 퀵정렬, 기수정렬(Radix Sort) 그 중 버블정렬과 선택정렬은 메모리 측면에서는 공간 복잡도 O(1)로 좋지만, 시간 복잡도는 O(n^2)로 비효율적이다. 반면 병합정렬과 퀵정렬은 시간 복잡도가 O(n logn)으로 조금 더 나은 성능을 보인다. 오늘은 배열을 정렬하는 문제를 통해 병합 정렬을 구현해보자. LeetCode - Sort an Array 병합 정렬은 가운데를 기점으로 배열을 반 씩 나눠 정렬 후 병합하는 방법이다. 읽는 것 보다 보는게 이해하기 더 쉽다. GeeksforGeeks의 예시 영상을 보자 : 링크 Python 코드 class Solution: def sortArray(self, nums): tmp = nu..

Q. 집합(set)의 모든 부분 집합(subset)들로 구성된 집합(power set)을 구하라 출처 : Cracking the Coding Interview - Q8.4 먼저 하나하나 적어보자. P([1]) = [[], [1]] P([1,2]) = [[], [1], [2], [1,2]] P([1,2,3]) = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]] 자세히 살펴보면 P(n)은 P(n-1)에 집합의 마지막 값을 하나 더 넣어준 것과 같다. 내 Python 코드 def subsets(nums: List[int]) -> List[List[int]]: subset = [[]] for num in nums: prevLength = len(subset) for i ..