[백준] 11722번 가장 긴 감소하는 부분 수열 (자바) : DP [실버 2]
✔️ 문제 설명 (펼치기)더보기문제수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 예제 입력 1 복사610 30 10 20 20 10예제 출력 1 복사3입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있..
2024. 8. 28.
[알고리즘] LIS : Longest Increasing Subsequnce 알고리즘 - DP 활용(최장 증가 부분 수열)
LIS (최장 증가 부분 수열)란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다. 예를 들어, 아래의 그림처럼 수열 {10, 50, 20, 30, 10, 60} 이 있을 때,만들 수 있는 증가하는 수열은 { 10, 50, 60 } 그리고 { 10, 20, 30, 60 } 이다. (이때, 꼭 등차수열이거나 순서가 연속적일 필요는 없다.)이때, 가장 긴 증가하는 부분 수열(LIS)은 { 10, 20, 30, 60 } 임을 알 수 있다. 백준 11053번의 가장 긴 증가하는 부분 수열 의 예시로 알고리즘을 설명하겠다. https://www.acmicpc.net/problem/11053 1. DP 테이블 정의하기수열의 크기가 n인 배열이 입력으로 주어지면, 우리는 i 번째 원소의 LIS..
2024. 8. 28.
[백준] 2748 피보나치 수2 (자바) : DP [브론즈2]
✔️ 문제 설명 (펼치기)더보기문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 10예제 출력 1 55 ✔️ 문제 풀이이 문제의 경우 이전에 풀었던 ..
2024. 8. 27.
