[Java] 백준 11444번 피보나치 수 6 - 도가뉴 항등식
https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n번째 피보나치 수를 찾아야 하는데, n의 최대값이 1,000,000,000,000,000,000이다. long 최대 범위 근접하는 엄청난 범위라서 도가뉴 항등식을 사용해야 한다. 단순히 재귀만 사용하면 시간복잡도를 많이 줄일 수가 없어서 TreeMap에 각 피보나치 수를 저장한다. 이미 저장된 값이 있다면 조회만 하면 끝! 시간복잡도 관리의 중요성을 상기시켜주는 문제였다. 참고로 m이 n보다 크거나 같아야 잘 동작하게 짜놓았다. import java.util.*; impo..
[Java] LIS - 최장 증가 부분 수열
https://sskl660.tistory.com/89 [Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence) *최장 증가 부분 수열(LIS, Longest Increasing Subsequence) ->최장 증가 부분 수열이란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 여기서 부분 수열은 연속적이거나, sskl660.tistory.com https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 ..
