날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. 풀이 : Binary Search 3. 설명 그림[1]과 같이 3개의 전깃줄을 제거하였을 때, 남아있는 모든 전깃줄이 교차하지 않음을 확인할 수 있다. 전봇대A를 기준으로 위치 1부터 10까지 차례대로 전깃줄을 연결하였을 때, 연결되는 전봇대 B의 위치 순서는 그림[2]와 같으며, 교차하지 않는 전깃줄은 최대 증가수열임을 알 수 있다. 마찬가지로, 전봇대 B를 기준으로 위치 1부터 ..

Algorithm/LIS 2021. 8. 17. 22:38

1. 문제 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 풀이 : Binary Search 3. 시간복잡도 : O(NlogN) 4. 설명 최장 증가 수열(LIS, Longest Increasing Subsequence) 문제이다. 그림[1]과 같이 LIS를 저장할 배열을 만든다. 상자를 처음부터 하나씩 LIS 배열에 위치를 찾아 넣는다. 위치를 찾을때에는 이분탐색을 사용하며, 동일한 크기의 상자가 들어올 수도 있으므로 lower bound를 ..

Algorithm/LIS 2021. 8. 9. 20:46