JADE's Repository

문제 문제 설명 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다. 당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 ..

문제 문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 코드 def solution(..

문제 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 코드 def solution(N, num..

■ 슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘이다. 정렬된 배열에 사용하는 투 포인터와 달리 정렬 여부와 상관 없이 사용된다. 크게 어렵지 않은 알고리즘이기때문에 바로 예제를 통해서 이해해보도록 하겠다. ■■ 다음 예제는 leetcode에서 가져왔다. 입력 : arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 출력 : [3, 3, 5, 5, 6, 7] k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최댓값들을 구하는 문제이다. 진행 순서는 다음과 같다. ■■■ 그럼 바로 코드 작성을 해보자 import sys from collections import deque def slidingwindow(arr:list, k..

■ Bool(부울) 연산은 크게 NOT, AND, OR, XOR이 있다. NOT 입력 출력 0 1 1 0 AND 입력1 입력2 출력 0 0 0 0 1 0 1 0 0 1 1 1 OR 입력1 입력2 출력 0 0 0 0 1 1 1 0 1 1 1 1 XOR 입력1 입력2 출력 0 0 0 0 1 1 1 0 1 1 1 0 ■■ 그렇다면 코딩에서의 비트 연산은 어떻게 표현할까? AND = & OR = | XOR = ^ NOT = ~ 간단하게 True와 False로 연산을 표현해보자. True & False = False True | False = True True ^ True = False ~ True = -2 어?! 그런데 ~ True의 출력 값이 not 1의 출력 값과 같은 0이 되어야하는 것이 아닌가? 자, 여..

■ 이진 검색은 정렬된 배열에서 값을 찾아내는 검색 알고리즘이다. 여기서 정렬된 배열이라는 부분이 아주 굉장히 중요하다. 또한 시간 복잡도는 logn으로 일정하다. 그렇다면 이진 검색 과정을 알아보자. 위 그림을 보면 이진 검색 과정을 한번에 이해할 수 있을 것이다. ■■ 이진 검색을 코드로 구현하는 방법은 대표적으로 [재귀, 반복, 모듈 사용] 총 3가지가 있다. 어려운 알고리즘은 아니니 코드 구현으로 바로 넘어가보자. Recursion def banarysearch(a:list, target:int): def search(left, right): if left target: return search(left, mid - 1) else: return mid else: return -1 return se..

문제 문제 설명 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.ss..

정렬은 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort ...... 등으로 겁나 많다. 하지만 난 이 중에 딱 3개(Bubble Sort, Merge Sort, Quick Sort)를 짚고 넘어갈 것이다. 버블 정렬 거두절미하고 말하면 버블 정렬은 중요하지 않다. 그냥 넘어가고는 싶지만 간단하게 설명하겠다. def bubblesort(a : list): for i in range(1, len(a)): for j in range(0, len(a) - 1): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] 위 코드를 보면 시간복잡도가 n^2이 되는 것을 알 수 있고 굉장..

■ 트라이는 검색 트리의 일종으로 문자열 탐색을 위한 자료구조로 널리 쓰인다. 초창기에는 '트리'로 발음했으나, 기존의 트리와 구분하기 위해 '트라이'라 부른다. 그리고 이진 트리가 아닌 다진 트리의 형태를 띤다. 위 그림과 같이 트라이가 있을 때 "appear"이라는 단어를 찾는다고 하면 a → p → p → e → a → r 순서로 문자열의 길이만큼만 탐색하면 원하는 결과를 얻을 수 있다. 트라이는 문자열을 위한 트리의 형태이기 때문에 사실상 문자 개수만큼 자식이 있어 상당히 많은 자식 노드를 갖고 있는 트리임을 확인할 수 있다. 위 그림을 봐도 그렇다고 느낄 것이다.... ■■ 트라이에서의 Leaf(리프) 노드 즉, 문자의 끝을 True, 나머지 상위 노드(문자)들은 False인 상태를 나타내며 구..

■ Heap(힙)은 트리 기반의 자료구조이다. 그리고 부모가 항상 자식보다 작은 구조이다. 그렇기때문에 루트가 가장 작은 값을 갖게되며 가장 작은 값을 추출하는 것은 루트를 추출한다는 것이 된다. 여기서 주의해야할 점은 Heap(힙)은 정렬된 구조가 아니다. 즉, 왼쪽 자식과 오른쪽 자식의 관계를 정의하지 않았다. 오직 부모, 자식 간의 관계만 정의하였다. 위 그림을 보면 오른쪽 노드가 왼쪽 노드보다 작은 것 (33, 17)이 있듯이 왼쪽과 오른쪽의 관계는 정의하지 않았다. 그리고 위 그림을 보면 자식이 두 개로 구성되어 있는데 이것을 Binary Heap(이진 힙)이라하며 트리 중 이중 트리가 많이 사용되듯이 힙도 이진 힙이 가장 많이 사용된다. 위 그림처럼 배열로 표현할 경우 대개 계산의 편이를 위해..