알루 코딩

Airflow는 파이썬으로 제작된 도구이자 워크플로우 생성시에도, 파이썬으로 구현해야 합니다 하나의 워크플로우는 DAG이라고 하며, DAG은 Directed Acyclic Graph 의 약자로, 방향성을 가진 그래프지만, 순환하지 않는 그래프를 말합니다. ( 보통 '댁'이라고 말합니다) DAG 안에는 1개 이상의 TASK 가 존재하며, TASK간 선후행 연결은 가능하지만, 순환되지는 않습니다. 보통 워크플로우(dag)는 다음과 같은 단계(task)를 거칩니다. 1. Rest API를 사용한 데이터를 받아서 전처리 2. 데이터를 DB에 넣기 전에 중복을 제거하기 위한 처리 3. 전처리한 데이터를 DB에 삽입 Cron 기반의 스케쥴링을 사용합니다. (리눅스에서 사용하는 기법으로, task들이 실행되어야 하는..

이 문제를 푸는 것에 있어서 O(n^2)으로는 바로 풀 수 있겠지만, 결과적으로 시간초과가 나고, follow up을 보면, 공간복잡도를 O(1)로 풀기를 제안하고 있습니다. 처음에 제가 접근한 방식은 배열의 길이를 2배로 늘려서 [1,2,3,4] 가 인풋 배열이라면, [1,2,3,4,1,2,3,4] 로 만든 후, 1을 바라볼 때는, [2,3,4] 의 곱을 2를 바라볼 때는 [3,4,1], 3을 바라볼 때는 [4,1,2], 4를 바라볼 때는 [1,2,3] 을 곱해서 결과 배열을 만드려고 했습니다. 위와 같은 방식으로 문제를 풀 때, 많은 변수들이 필요했고, 파이썬의 for문을 돌면서, index를 다시 뒤로가도록 하는 것에 있어서 어려움을 겪었습니다. 결국, 저는 문제를 O(n)의 방식으로 30분만에 풀..

이 문제는 지난 PreOrder 문제에 이어 Level Order Traversal 문제입니다. Level Order는 말그대로 레벨 순으로 순회를 하는 것인데, 트리에서는 보통 root 노드부터 레벨 1로 시작되고 아래로 내려오면서 level이 증가합니다. 해당 문제에서는 레벨별로 노드를 묶는 것이 관건인데요, 코드를 살펴보면서 설명드리겠습니다. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right from collections import deque ..

리트코드에서의 1번문제입니다. 문제를 설명해보자면, 입력값으로 nums 라는 숫자배열이 주어집니다. 그리고 target값도 입력값으로 주어지는데요, nums배열에서 두 숫자를 더해 target을 만들 수 있다면, 해당 두 숫자의 인덱스 값을 배열 형태로 출력하는 문제입니다. 문제 자체는 비교적 간단한 문제입니다만, 이 문제를 어떻게 효율적으로 풀어야 할지는 고민해봐야 할 부분입니다. 해당 문제를 직관적으로 풀자면 for문을 두 번 돌면 됩니다. 대략적인 코드는 아래와 같겠죠. for i in range(len(nums)): for j in range(i+1,len(nums)): if (nums[i] + nums[j]) == target: return [i,j] 하지만, 위와 같이 푼다면, 이미 시간복잡도..

이 문제는 전형적인 bfs,dfs 문제입니다. 문제 설명을 간단히 하자면, 주어진 image 그래프에서 (sr, sc) 위치에서부터 시작해 상,하,좌,우 4방향을 탐색하면서 image[sr][sc]와 값이 같다면, 해당 자리를 color 값으로 치환하는 문제입니다. 간단히 말해서, 시작하는 위치와 값이 같으면서 연결된 자리를 color 값으로 바꾸면 됩니다. 먼저, 코드를 살펴보면서 설명을 해보겠습니다. import copy class Solution(object): def floodFill(self,image, sr, sc, color): """ :type image: List[List[int]] :type sr: int :type sc: int :type color: int :rtype: List[L..

주어진 문자열 s를 이용해서 만들 수 있는 가장 긴 팰린드롬을 구하는 문제입니다. 문자열 s는 대문자와 소문자가 구분해서 주어지고 만들어 질 수 있는 가장 긴 팰린드롬의 길이를 답으로 출력하면 됩니다. 처음에 접근했던 방법은 Discussion에서 해당 코멘트를 봤습니다. 한 유저가 남긴 코멘트였는데, 해시맵을 사용하면 된다고 해서 바로 딕셔너리를 생각해봤습니다. 주어진 문자열에서 문자가 나온 횟수를 value로 저장하고, 해당 문자를 key값으로 저장하는 딕셔너리를 생각해본다면, 가장 긴 팰린드롬의 길이는 짝수의 횟수를 가진 key값과 홀수값 중에서 최댓값을 가진 key값의 구성으로 만들어지겠다라는 것이 추론됩니다. 예를 들어서 설명해볼까요? "aabbsserrr" 이라는 문자열이 있다고 하면, 이 문..

위 문제는 그리디 문제입니다. 리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠. 맨 처음에 저는 O(n^2))의 복잡도로 문제를 풀었습니다. 그래서, 시간초과의 문제에 걸렸습니다. 제약조건을 보면 prices의 길이가 최대 100000이기 때문에, O(n^2)의 복잡도로 풀어버리면 10의 8승을 넘기 때문에 시간초과에 걸리는 것은 당연한 소리겠죠! 처음, 시간초과에 걸렸던 코드는 아래와 같습니다. class Solution: def maxProfit(self, prices: List[int]) -> int: is_reversed_sorted = all(prices[i] >= prices[i+1] for i in range(len(prices)-1)) if is_reversed_sorted: retur..

위 문제는 정렬된 두 리스트를 병합하는 문제입니다. 단순 알고리즘 문제를 푸는 것이 아니라 자료구조를 고려해서 풀어야 하는 문제였는데요, 자료구조의 필요성이 느껴진 문제이기도 했습니다. 문제를 접근하는 방식에는 2가지 방법이 있는데요, 하나는 재귀적 알고리즘을 사용하는 방법과 두번째로는 더미노드를 만들어 그 뒤에 이어 붙이는 방법이었습니다. 시간 복잡도는 둘다 O(n+m)이 나오는데요, 두 번째 방법으로 푼 코드를 살펴봅시다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeT..

이 문제는 주어진 문자열 t 안에 s문자열이 있는지 아닌지를 판단하는 문제입니다. 예를 들어서, t가 ahbgdc 이고, s가 abc 라면, ahbgdc에서 h,g,d,를 제거하면 abc가 되므로 true를 반환합니다. 반면, 만약 t가 abcde이고, s가 aec 라면, abcde 문자열에서 어떤 수를 써서라도 aec를 만들 수 없기에 false를 반환합니다. 즉, t의 원래의 문자열에서 순서는 유지한 채 수열을 이루는 항 중에 일부만 모아 s가 만들어진다면, true를 반환하고, 그렇지 않다면 false를 반환하면 됩니다. 코드를 통해 살펴보죠. class Solution: def isSubsequence(self, s: str, t: str) -> bool: idx = 0 cnt = 0 if len..

주어진 문자열 s와 t가 동형사상이라면, true를 반환하고, 그렇지 않으면, false를 반환하는 문제인데요! 다양한 문제풀이가 있을거에요. 딕셔너리를 이용해서 풀어도 되고, 자바를 활용한다면 해시맵으로도 풀 수 있을 것 같습니다! 저도 처음에는 딕셔너리로 접근을 했다가, index의 위치만 저장하는 리스트로 풀어도 되겠다 싶어서 리스트만을 이용했습니다. 코드를 보면서 살펴보겠습니다. class Solution: def isIsomorphic(self, s: str, t: str) -> bool: answer = False if len(s) != len(t): return answer else: s_check = [] t_check = [] for i in s: s_check.append(s.index..