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

문제 링크 : https://www.acmicpc.net/problem/1167 트리는 순환하지 않는다는 특징을 가지고 있고그렇기에 위에 문제에서 하나의 정점에서 다른 하나의 정점까지의 거리는 하나가 나온다.트리의 임의의 정점을 2개 골랐을 때 그 정점사이의 거리가 가장 긴 경우를 지름이라고 한다. 단순히 생각해보면 모든 정점 간의 거리를 구하면 될 것 같지만 정점의 수가 100,000 이기 때문에 시간초과가 발생한다.따라서 탐색의 범위를 줄여야 한다. 해당 문제를 풀때 아이디어는 임의의 한 정점에서 시작해서 다른 정점까지의 거리를 모두 구한 뒤 그중가장 멀리있는 정점이 해당 트리의 지름의 한 끝점이라는 것이다. 트리의 지름의 한 끝점을 구할 때 BFS를 한번 쓰고, 해당 끝점에서 BFS를 사용하여 각 ..

문제 링크 : https://www.acmicpc.net/problem/1377 문제를 접근하면 C++ 을 이용하여 정렬을 하는데 이때 버블 소트 알고리즘을 이용해서 정렬 하였다.위 문제에서는 오름차순 정렬을 하고있다.버블 소트 알고리즘은 배열에서 arr[i] 값과 arr[i+1] 값을 비교하여 만약 arr[i] 값이 더 크다면arr[i]와 arr[i+1] 의 값을 swap 한다. 이런식으로 하나하나 값을 비교하며 정렬하기 때문에정렬에 필요한 시간복잡도는 O(N^2)이 된다. 해당 문제에서 C++ 로 작성된 코드를 보면스왑이 한번도 일어나지 않는경우의 i의 값을 출력하는것을 알 수 있다. 단순히 위의 C++ 코드로 구현된 버블 소트 알고리즘을 자바로 옮겨서 풀 수 있지만문제는 문제의 입력값이 최대 500..

링크 : https://www.acmicpc.net/problem/1874 문제의 이름부터 대놓고 스택 수열 이기 때문에 스택을 이용해서 해결하면 된다.자연수 1부터 N까지 순차적으로 stack에 push 해야 한다는 조건이 있으므로이 부분만 유의하면 된다. 로직을 간단히 생각해보면 자연수를 num = 1; 로 선언하고,주어진 수열을 4,3,6,8,7,5,2,1 이라고 했을때수열을 하나씩 순회하면서 현재 값을 now 라고 한다면 1. stack 이 비어있을땐 num넣고, num++;2. stack의 마지막 값이 now 보다 작다면 num넣고, num++;3. stack의 마지막 값이 now와 같다면 pop();4. stack의 마지막 값이 now보다 작다면 -> 이 경우에는 스택연산으로 해당 수열을 만들..