고양이 두 잔

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 동적계획법의 유명한 문제라고 알려진 가장 긴 증가하는 부분수열(LIS - Longest Increasing Subsequence) 문제이다. 예전에 한 번 풀었던 풀이를 보니 탑다운 방식으로 구성..

알고리즘 문제를 이리저리 돌려가며 풀다가 Map을 스트림으로 다룰 때의 자료형이 필요했다. 일단 인텔리제이에서 알려주는 대로 사용해서 문제를 풀고, 따라가며 공부하기. Map.Entry 소개부터 하자면 Map.Entry는 자바 컬렉션 프레임워크의 Map 인터페이스의 내부 인터페이스이다. Map과 마찬가지로 키-값의 데이터를 저장하며, Map에서 .entrySet() 연산자를 호출하면 생성할 수 있다. 정확하게 말하자면 .entrySet()의 경우 이름 그대로 아래와 같은 Set을 생성하며, Map integerMap = new HashMap(); Set set = integerMap.entrySet(); 위 Set에 모든 엔트리 객체가 담겨있기 때문에 개별 Map.Entry를 제어하려면 그대로 스트림을..