[백준 java] 11054 - 가장 긴 바이토닉 부분 수열
11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 내가 푼 방법 가장 긴 증가하는 부분수열과 감소하는 부분수열을 합친 문제이다. 나는 기준점 (idx) 을 잡아 그 기준점보다 낮은 인덱스는 LIS 알고리즘을 그리고 높은 인덱스는 LIS를 뒤집어 사용하여 감소하는 부분 수열을 구현하였다. 10 1 5 2 1 4 3 4 5 2 1 만약 위 예제에서 idx = 3을 조사한다 하면 arr[3]을 기준으로 { 1, 5, 2 } 를 오름차순 긴 부분수열을 구하고, { 2, 1, 4, 3, 5, 2, 1 } 을 내림차순 긴 부분수열을 구한다 이..
[백준 java] 11722 - 가장 긴 감소하는 부분 수열
11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net [백준 java] 11053 - 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부 dwc04112.tistory.com 위 문제와 매우 유사한 문제이다. 이번에도 dp에 해당 숫자로 ..
[백준 java] 11053 - 가장 긴 증가하는 부분 수열
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 부분 수열(Longest Increasing Subsequence) 알고리즘으로 풀 수 있는 문제이다. 어떤 수열이 주어지면 그 수열 내에서 (변형x) 오름차순으로 구성된 가장 긴 수열을 LIS 라고 한다. 이 알고리즘을 사용하기 전에는최소값 index를 구하여 해당 index부터 최장거리를 구하려고 했는데중복되는 최소값이 있으면 길이를 구하지 못해서 바로 틀렸다... [BO..
[백준 java] 10884 - 쉬운 계단 수
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제풀이 첫째줄 n을 입력받는다. 여기서 n은 자릿수를 나타낸다 n=2 두자릿수 중 계단 수를 찾는다. (총 17개) 1 : 10, 12 (2개) 2 : 21, 23 (2개) 3 : 32, 34 (2개) 4 : 43, 45 (2개) 5 : 54, 56 (2개) 6 : 65, 67 (2개) 7 : 76, 78 (2개) 8 : 87, 89 (2개) 9 : 98 (1개) 만약 n이 3이라면 n=3 1 : 123, 121, 101 (4개) 2 : 210, 212, 232, 234 (4개) 두번째 자릿수의 경우의 수는 n=2에서 구한 갯수가 들어간다. 예를들어 첫번째 자릿수가 2이면 두..
