오늘은 뭐 할까?

TreeNode 정의class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right 문제에서 주어진 root의 경우 아래처럼 출력이 되게 된다[TreeNode{val: 3, left: TreeNode{val: 9, left: None, right: None}, right: TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}]  BFS를 이용한 풀이class So..

트리Degree : 자식 노드의 개수Size : 자기 자신을 포함한 모든 자식 노드의 개수High : 현재 위치부터 Leaf까지의 거리Depth : 루트에서부터 현재 노드까지의 거리트리는 루트에서부터 시작하며 루트는 자식을 가지고 자식은 부모와 Edge(간선)으로 연결되어 있다. 트리는 그래프와 비슷하게 보이기 때문에 트리 = 그래프라는 의문점이 생길수도 있지만그래프와는 아주 큰 자이점이 있는데, 바로 트리는 항상 단방향이기 때문에 순환구조를 가질 수 없다얼핏 보면 DAG도 순환하지 않기 때문에 이것은 그래프가 아니라 트리라고 봐야하지 않을까라는 생각이 들수도 있는데트리의 경우 그래프와는 다르게 단 하나의 부모노드를 가진다는 특성을 가지고 있기 때문에 DAG를 트리라고 생각하는 것은 잘못된 것이라 할 수..

List를 이용한 풀이class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: q = [] if not head: return True node = head while node is not None: q.append(node.val) node = node.next while len(q) > 1: if q.pop(0) != q.pop(): return False return True List의 경우 pop()으로 첫 번째..

연결 리스트 (Linked List)데이터가 연속된 공간에 저장되어 있지 않고, 떨어져 있더라도 연속된 공간에 저장되어 있도록 하는 리스트동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 된다데이터를 구조체로 묶어 포인터로 연결되어 있다배열과 달리 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 한다연결 리스트 핵심요소Node : 연결 리스트의 기본 단위데이터 필드 : 노드에 저장된 데이터링크 필드 : 다음 노드를 가르킨다Head : 연결 리스트에서 가장 처음 위치하는 노드, 리스트 전체를 참조하는데 사용Tail : 연결 리스트에서 가장 마지막에 위치하는 노드, Tail 노드의 링크 필드는 Null을 저장하고 있다 연결 리스트 구현 (Python..

첫 번째 풀이def solution(weights): w = list(set(weights)) w_set = sorted(w) w_dict = dict.fromkeys(w_set, 0) for _ in weights: w_dict[_] += 1 cnt = 0 for _ in w_set: if w_dict[_] >= 2: cnt += (1 / 2) * w_dict[_] * (w_dict[_] - 1) n = len(w_set) for i in range(n - 1): for j in range(i + 1, n): if w_set[i] * 2 == w_set[j]: ..

Airflow의 구성요소DAG작업 실행 순서를 정의, 작업간의 종속성을 지정각 작업들이 서로 순환하는 것이 아니라 일방적인 통행 방향을 가지고 있음 SchedulerDAG 파일을 읽고 종속성에 따라 작업을 트리거하고 실행을 추적, DAG 폴더에 저장된 모든 작업과 동기화를 유지하고 시작할 수 있는지 확인 Executor / Worker실행중인 작업을 처리하는 실행 프로그램Executor는 별도의 구성요소가 아닌 스케줄러의 구성 요소, 스케줄러 프로세스 내에서 실행됨Production을 위한 Airflow 작업에서는 Worker에게 작업을 전달 Metadata database 사용자의 권한, 과거 및 현재 DAG, DAG 구성에 대한 정보 저장, 스케줄러의 정보 소스 역할 Webserver웹으로 사용자 인..

배열을 하나로 분리해서 다시 합치면서 정렬하는 알고리즘시간 복잡도  : $O(nlog_2n)$ 예시[6, 5, 3, 1, 8, 4, 7, 2]# 1. 배열을 반으로 나누기[6, 5, 3, 1] [8, 4, 7, 2]# 2. 배열의 개수가 하나가 될때까지 나누기[6, 5] [3, 1] [8, 4] [7, 2][6] [5] [3] [1] [8] [4] [7] [2]# 3. 두 개씩 낮은 숫자을 비교하여 정리하면서 합치기[5, 6] [1, 3] [4, 8] [2, 7][1, 3, 5, 6] [2, 4, 7, 8][1, 2, 3, 4, 5, 6, 7, 8]  코드 구현def mgsort(arr): if len(arr)

지정된 값(Pivot)을 기준으로 지정된 값 보다 작은 값과 큰 값으로 나누어 정렬하는 알고리즘분할 (Divide) : pivot을 중심으로 정렬할 자료를 2개의 부분집합으로 나눔정복 (Conquer) : 부분집합의 원소 중 pivot보다 큰 값과 작은 값으로 나눔부분집합이 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행시간 복잡도 : 평균 수행 시간 복잡도 $O(log_2n)$, 최악의 수행 시간 복잡도 $O(n^2)$코드 구현def qsort(arr): if len(arr) == 0: return [] pivot = arr[0] equl = [pivot] high = [] low = [] for i in range(1, len(arr)): ..

첫 번째 풀이def solution(x, y, n): answer = 0 sum_ls = [x] while sum_ls: if y in sum_ls: return answer sum = [] for ls in sum_ls: if ls + n    BFS를 이용한 문제로 문제에서 사용할 수 있는 모든 연산을 사용해서 계산 후 y를 넘는 것은 계산 대상에서 제외하고 반복해서 계산하는 방식으로 코드를 작성하였다 대부분의 테케가 잘 풀렸지만 몇몇이 시간초과가 나서 어느 부분에서 그런지 생각해 봤지만 잘 떠오르지는 않았다 두 번째 풀이def solution(x, y, n): answer = 0 ..

첫 번째 풀이def solution(numbers): answer = [-1] * len(numbers) for i in range(len(numbers)): n = numbers[i] for j in numbers[i + 1 :]: if j > n: answer[i] = j break return answer처음엔 직관적으로 numbers의 값을 차례로 가져오고 가여운 값 다음 인덱스부터 새로운 인덱스로 만들어 가져온 값과 비교했다 당연히 이중 for문을 사용했기 때문에 시간초과가 걸리지 않을까...? 했지만.. 역시나.. 시간이 오래 걸리기도 하고, 테스트 10번 이..