거누의 개발노트

문제 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 입력 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가지가 있다고 한다. 이..

문제 정수 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 =..

해시테이블? 해시 테이블 또는 해시 맵은 키를 값에 맵핑할 수 있는 구조로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 해시 테이블의 가장 큰 특징은 시간 복잡도가 O(1) 이라는 점이다. 덕분에 데이터에 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수? 해시함수는 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 반환 시켜주는 함수이다. 입력값의 길이가 달라도 출력값은 언제나 고정된 길이로 반환한다. 동일한 값이 입력되면 언제나 동일한 출력값을 보장한다. ex) AFJQ..