JADE's Repository

문제 문제 설명 고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는..

문제 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 compute..

문제 문제 설명 일렬로 나열된 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이 되는 것을 알 수 있고 굉장..