량베개

최장 증가 부분 수열(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 알고리즘 중 하나인 크루스칼 알고리즘을 사용하였다.현재 선택 가능한 간선 중 최소 비용의 간선을 선택하는 탐욕법에 속하는 알고..