거누의 개발노트

트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조이다. 큐(Queue)와 스택(Stack)은 자료구조에서 선형 구조라고 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 트리구조는 위 그림에서 보는 것 처럼 폴더 구조와 같습니다. 이진 트리 이진 트리는 최대 두 개의 자식을 가집니다. ( 0, 1, 2 ) 완전 이진 트리 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있습니다. 마지막 레벨은 꽉 차 있지 않아도 되지만, ..

문제 이진 트리가 주어지면 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..

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 입력 TreeNode [1,2,3,4,5] 출력 3 먼저 내 코드에서 테스트 해보려면 배열을 리스트로 만드는 과정이 필요했다. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def make_tree_by(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value == None: return parent = TreeNode(value) parent.left = make_tree_by(lst, 2 * idx + 1) ..

문제 [문제 설명] △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다. 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가..

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

디지털 시스템은 10진수를 사용하지 않고 모든 유형의 정보를 2진수로 표현한다. 십진수 십진수를 한자리로 표현하면 0 부터 9까지 10개의 숫자는 표현가능하다. 두자리 숫자는 0 부터 99까지, 세자리는 0 부터 999 까지 표현 십진수는 10의 거듭제곱의 합을 줄여 표기한 것이라고 생각하면 된다. 예를들어서, 1867은 1 x 10³ + 8 x 10² + 6 x 10¹ + 7 x 10⁰ 으로 1 x 1000 + 8 x 100 + 6 x 10 + 7 x 1로 표현 할 수 있다. 이진수 일련의 비트가 주어졌을 때, 각 자리의 숫자들을 10대신 2를 기수로 표현하고 0과 1만 사용하여 숫자를 표현하는 수다. 11101 같은 이진수는 1 x 2⁴ + 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰..

문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음 {if} 으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. { sort } 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이..