백준 12015 가장 긴 증가하는 부분 수열 2 (Java)
https://www.acmicpc.net/problem/12015 1. 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.2. 풀이기존에 사용하던 LIS 코드는 다음과 같다.for(int i=1;i 이렇게 구현하면 시간복잡도는 O(n^2)가 된다...
백준 22866 탑 보기 (Java)
1. 문제일직선으로 다양한 높이의 건물이 총 N개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다. i번째 건물 기준으로 i−1, i−2, ..., 1번째 건물은 왼쪽에, i+1, i+2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다.바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다.번호12345678높이37163517보이는 건물 번호2x2, 4, 82, 82,4,6,82,4,82,4,6,8x각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.입력첫번째 줄에 건물의 개수 N이 주어진다.두번째 줄..
