거누의 개발노트

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

문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 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..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 예제 입력 5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 1 0 0 1 작성한 코드 import sys n1 = int(sys.stdin.readline()) lst1=list(map(int, sys.stdin...

문제 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴 입력 abcabcbb bbbbb pwwkew 출력 3 1 3 작성한 코드 def lengthOfLongestSubstring(s: str) -> int: used = {} max_length = 0 start = 0 for i, v in enumerate(s): if v in used and start

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 ..

문제 원형 큐를 디자인하라. 초기 셋팅 class MyCircularQueue: def __init__(self, k: int): def enQueue(self, value: int) -> bool: def deQueue(self) -> bool: def Front(self) -> int: def Rear(self) -> int: def isEmpty(self) -> bool: def isFull(self) -> bool: 입력 ["MyQueue","push","push","peek","pop","empty"] [[],[1],[2],[],[],[]] 출력 [null,null,null,1,1,false] 작성한 코드 class MyCircularQueue: def __init__(self, k: int):..

문제 정렬되어 있는 두 연결 리스트를 합쳐라 입력 1->2->4 1->3->4 출력 1->1->2->3->4->4 책에 있는 코드 class solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if (not l1) or (l2 and l1.val > l2.val): l1, l2 = l2, l1 if l1: l1.next = self.mergeTwoLists(l1.next, l2) return l1 찾은 코드 # 이해하기 쉬운 풀이 def mergeTwoLists(list1, list2): if (list1 == None and list2 == None): return None head = result = ListNode()..