자바

문제 링크 : https://www.acmicpc.net/problem/1197 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘 구현 문제이다.MST 알고리즘은 모든 노드들을 연결했을 때 가장 적은 비용의 간선 집합을 찾는 알고리즘이다.간단한 MST에 대한 설명은 아래와 같다.  위와 같은 그래프가 있다고 가정한다.정점 사이에는 가중치가 있는 간선이 있다.MST 알고리즘은 해당 그래프의 모든 정점들을 잇는 가장 최소비용의 간선 집합을 찾는 알고리즘이다.여기서 중요한 것은 그래프를 사이클이 생기면 안 된다는 것이다.사이클이 존재하면 가중치의 합이 최소가 될 수 없기 때문이다.또한 정점의 개수가 V라고 하면 정점을 최소 신장 트리를 구성하는 간선의 개수는 무조건 V-1개..

문제 링크 : https://www.acmicpc.net/problem/1715 문제를 처음 접하고 예제 입력만을 가지고 단순히 생각해 보면 숫자 카드 묶음을 1차원 배열로 만들고 이를 오름차순 정렬해서 앞에서부터 더해 나가면 되지 않을까 생각할 수 있지만그건 오름차순으로 정렬하고 가장 작은 값들 2개를 골라 더한뒤 그다음 작은 값이 배열의 다음 값인 경우에만 가능하다예를 들어 문제의 예제처럼 10, 20, 40 일 경우에는(10 + 20) = 30 이고 해당 값 다음으로 큰 값이 40이기 때문에 단순 1차원 배열에서 오름차순 정렬로 풀 수 있다. 하지만 만약 주어진 카드 묶음이 10, 10, 10, 10, 10이라고 하면오름 차순 정렬 후 가장 작은 2개의 값은 10, 10 이기때문에 둘을 합치면 20..

문제 링크 : https://www.acmicpc.net/problem/1300 문제를 풀어서 보면 단순히 2차원 배열의 값들을 1차원 배열로 옮겨서 오름차순으로 정렬한 뒤K번째 인덱스(1부터 시작)의 값을 출력하면 되는 문제다. 하지만 N의 값이 최대 10^5 이기 때문에 이를 2차원 배열 N*N으로 만든다면 최대 10^10 개의 값들이 생성된다.따라서 단순히 2차원 배열의 값을 1차원 배열로 옮겨서 해결할 수는 없다. 따라서 다른 풀이를 생각해야 한다.먼저 문제 조건에 따라 3 * 3 배열을 1차원 배열로 전환하고 오름차순 정렬하면1 2 2 3 3 4 6 6 9가 되는 것을 알 수 있다.이때 K번째 인덱스의 값은 절대 K값 이상이 될 수 없다는 것을 알 수 있다. 따라서 K번째 인덱스의 최댓값은 K,..

문제 링크 : https://www.acmicpc.net/problem/2343 연속된 배열에서 M개의 블루레이에 모든 기타 강의 동영상을 녹화할 때 블루레이의 최소 크기를 구하는 문제다.N이 100,000 이기 때문에 완탐은 불가능하고강의의 순서는 변경되지 않는다는것에서 이진탐색을 사용하면 풀 수 있다는 힌트를 얻어야 한다. 이진탐색의 시작과 끝 인덱스를 찾아야 하는데여기서 시작인덱스는 주어진 강의중 가장 시간이 긴 강의의 시간(만약 블루레이의 개수 M 이 N이라고 한다면 블루레이 하나당 최소한의 크기는 N개의 강의중 가장 시간이 긴 강의가 되기 때문) 끝 인덱스는 만약 M이 1이라고 한다면 모든 강의를 전부 포함해야 하기 때문에 모든 강의시간들의 합이 끝 인덱스가 된다. 따라서 시작 인덱스(가장 시간..