거누의 개발노트

문제 이진 트리를 직렬화 및 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방식에는 제한이 없습니다. 이진 트리를 문자열로 직렬화할 수 있고 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인하기만 하면 됩니다. 입력 Input: root = [1,2,3,null,null,4,5] 출력 Output: [1,2,3,null,null,4,5] 작성한 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): q..

문제 BST에서 노드의 값이 val과 같은 노드를 찾고 해당 노드의 하위 트리를 반환하는 코드를 작성. 그러한 노드가 존재하지 않으면 null을 반환 합니다. 입력 Input: root = [4,2,7,1,3], val = 2 출력 Output: [2,1,3] 작성한 코드1 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Opt..

문제 이진 탐색 트리의 노드와 두 개의 정수 low와 high 가 주어지면 포함 범위 에 있는 값을 가진 모든 노드의 값 합계를 반환하는 코드를 구현하시오. 입력 Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 출력 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32. 작성한 코드1 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.ri..

문제 이진 트리가 주어지면 root트리를 반전 하고 루트 를 반환합니다. 입력 root = [4,2,7,1,3,6,9] 출력 [4,7,2,9,6,3,1] 작성한 코드 # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def list_to_tree(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value is not None: parent = TreeNode(value) parent.left = list_to_tree..

문제 동일한 값을 지닌 가장 긴 경로를 찾아라. 입력 Input: root = [5,4,5,1,1,5] 출력 Output: 2 처음에 지나온 노드의 개수 인줄 알고 엥? 왜 2개이지 한참 고민했다. 출력을 다시 생각해보니 간선의 개수였다... 아무튼 이 문제도 처음 접근하는 나에게는 어려운 친구들이었다. 역시 그냥은 잘 안 풀려서 책에 도움을 받았다. 뭐 어떤가..잘 이해해서 내걸로 만들면되지! def longestUnivaluePath(root) -> int: rtn = [0] def dfs(node:TreeNode): if node is None: return 0 #왼쪽 노드 값도 구해와 줄래? left = dfs(node.left) #오른쪽 노드 값도 구해와 줄래? right = dfs(node.r..

이번주는 폭풍의 시간이 었다. 자료구조를 배우고 알고리즘을 배우고 빠르게 진행된다. 빠르게 배우고 적용시켜서 문제를 풀려고 해도 잘 풀리지 않는게 코딩테스트 문제인거 같다. 1일차에는 알고리즘 개요와 배열을 간단히 배운다. (간단하지만 간단한게 아니다.) 알고리즘 개요 점근 표기법 알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법 점근 표기법의 종류 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있다. 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기하는것이다. 예를 들어 빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 ..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 예제 입력 3 4 7 10 예제 출력 7 44 274 작성한 코드 import itertools import sys N = int(sys.stdin.readline()) case = [int(sys.stdin.readline().strip()) for _ in r..

문제 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. 입력 "23" 출력 ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'] 작성한 코드 def letterCombinations(digits: str) -> List[str]: if digits == '': return [] phone = [[],['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']] lst = [int(i) for i in digits] l = [phone[i-1] for i in lst] pro =..