whilescape

문제 설명 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. 제한 사항 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니다. 접근법 >> heap 을 이용하여 풀었다. >> 남은 시간이 제일 큰 work부터 차례대로 처리해 나간..

문제 설명 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다. [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요. 제한사항 n은 20이하의 자연수 입니다. k는 n! 이하의 자연수 입니다. 접근법 >> 첫 시도 : 내가 만든 next_perm_generator 함수를 이용하는 방법 >> 1번 perm으..

문제 설명 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 제한사항 표(board)는 2차원 배열로 주어집니다. 표(board)의 행(row)의 크기 : 1,000 이하의 자연수 표(board)의 열(column)의 크기 : 1,000 이하의 자연수 표(board)의 값은 1또는 0으로만 이루어져 있습니다. 접근법 >> 최종 접근법 : dynamic programming >> 사실, 내가 어떤 느낌을 갖고 작성하긴 했지만 >> 느낌 수준을 넘어 타당성을 확실히 확보해야 한다. >> 타당..

문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 접근법 >> 이미 0이 없는 6진법 체계에 대한 변환 함수를 만들어 본 경험이 있다. >> 루빅스큐브 노드 탐색시에 0이 없는 6진법 체계를 사용하..

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

공부해보면서 python으로 테스트 해봅니다. 19년 6월에 c로 한번 구현 해봤지만, 역시 반복이 중요 출처 : C로 배우는 알고리즘/활용 알고리즘편/이재규 지음/도서출판 세화 1. 집합 집합 개론 >> 명확히 구별 가능한 원소들의 집단 >> 특징 : 구별 가능함, 무순서 >> 구별 가능함 : 어떤 집합이 있을 때, 임의의 원소가 그 집합에 포함되는 것인지 아닌지 명확히 구분할 수 있음 >> 무순서 : 집합을 구성하는 원소들 사이에는 순서가 없다. 집합을 다루는 문제는 두 가지로 압축 가능 >> 1. 검색(find) 문제 : 어떤 원소가 어떤 집합에 포함되는지 아닌지를 알아내는 문제 >> 2. 결합(Union) 문제 : 두 개의 서로 다른 집합을 하나의 집합으로 합치는 문제 집합을 표현하는 방법 >> ..

문제 설명 n개의 구별 가능한 요소에 의해 만들어진 n!의 perm 집합이 있다. 그 집합을 오름차순으로 정렬한다. 그 집합의 한 원소를 input으로 넣으면 다음 차례의 perm을 반환하는 함수를 작성하여라 디테일 function prototype : def solution(n, prevperm) when n = 4, prevperm = [], function return [0,1,2,3] when n = 4, prevperm = [0,1,2,3], function return [0,1,3,2] when n = 4 prevperm = [3,2,1,0], function return [] 주저리 어디선가 풀어본 문제 그렇지만 머리에 확실하게 남아있지 않은 문제 그래서 이 공간에 확실하게 기록하여 내 머리..

문제 설명 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요. ..