[알고리즘 문제] 백준11054 - 가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉이라고 처음 들어봤다. 설명에서는 " S1 Sk+1 > ... SN-1 > SN " 인수라고 한다.... {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 아니라고 하는데, 아무튼 쭉 오름차순이거나..
2020. 4. 4.
[알고리즘 문제] 백준11722 - 가장 긴 감소하는 부분 수열
https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net LIS와 반대로 가장 긴 감소하는 부분 수열을 구하는 문제 입니다. LIS의 경우 첫번째 ~ i번째 수를 검사하지만 가장 긴 감소하는 부분 수열은 i ~ 마지막 부분을 검사해야 합니다. 2가지 방법으로 풀어봤는데, 첫번째 방법은 배열을 뒤집어 LIS처럼 구하는 방식이고, 두번째 방법은 배열을 안뒤집고..
2020. 4. 4.
[알고리즘 문제] 백준11053 - 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 최장 증가 수열(Longest Increasing Subsequence), LIS라고 불리는 문제 입니다. [10, 20, 10, 30, 20, 50]가 있을 때 증가하는 부분 수열을 구해보면 다음과 같습니다 [10,20] [10,20,30] [10,20,30,50] [20,30] [20,30,50]..
2020. 4. 4.