량베개

2152번 여행 계획 세우기 P2  문제평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000) 개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을 거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다. 태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000) 개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N) 번 도시에서 시작해서 T(1 ≤ T ≤ N) 번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.도..

프로그래머스 야근 지수 LV3 문제 설명회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.제한 사항works는 길이 1 이상, 20,000 이하인 배열입니다.works의 원소는 50000 이하인 자연수입니다.n은 1,000,000 이하인 자연수입니다.입출력 예worksnresult4[4, 3, 3]121[2, 1, 2]63[1, 1..

17297번 Messi Gimossi G4 문제메시는 축구 선수이다. 메시는 기분이 좋다.messi(1): Messimessi(2)​​: Messi Gimossimessi(3)​​​​​​: Messi Gimossi Messimessi(4): Messi Gimossi Messi Messi Gimossimessi(5): Messi Gimossi Messi Messi Gimossi Messi Gimossi Messi메시의 외침은 피보나치수열과 유사하게 정의된다.messi(N)은 messi(N-1), 공백, messi(N-2)을 차례로 이어붙여서 만든 문자열이다. 욱제는 N이 충분히 클 때, messi(N)의 M번째 글자가 뭔지 궁금해졌다.입력정수 M이 주어진다. (1 ≤ M ≤ 2^30-1)출력N이 충분히 클..

1516번 게임 개발 G3  문제숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 ..

최장 증가 부분 수열(LIS)에 해당하는 문제 시리즈이다.입력과 출력, 시간 복잡도와 수의 범위에 따라 S2에서 P5까지 난이도가 준비되어 있다. 문제를 풀 당시에는 1 -> 4 -> 2 -> 3 -> 5 순으로 풀이했다.LIS를 처음 접한다면 위 순서대로 푸는 것이 좋을 것이라 생각한다. 11053번 가장 긴 증가하는 부분 수열 / S2수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있..

문제 설명n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.입출력 예ncostsreturn4[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]4 N개의 섬을 잇는 다리의 최소 비용을 구하는 문제로 요약이 가능하다. MST 알고리즘 중 하나인 크루스칼 알고리즘을 사용하였다.현재 선택 가능한 간선 중 최소 비용의 간선을 선택하는 탐욕법에 속하는 알고..