[백준(baekjoon) 11054] 가장 긴 바이토닉 부분 수열 문제 백준 11054 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 바이토닉 부분 수열 중 가장 긴 길이를 출력. 바이토닉 수열 : S1 Sk+1 > … SN-1 > SN을 만족하는 수열 예시 : {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10} 주의 : 증가, 감소 수열도 바이토닉 수열에 속한다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 여기서 다른 점은, 증가하는 부분과 감소하는 ..

[백준(baekjoon) 11722] 가장 긴 감소하는 부분 수열 문제 백준 11722 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 감소하는 부분 수열 중 가장 긴 길이를 출력. 예시 : A = {10, 30, 10, 20, 20, 10} 인 경우, A = {30, 20, 10} 이고 길이는 3이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 1.import java.u..

문제 백준 11055 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 큰 합을 출력. 예시 : A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우, A = {1, 2, 50, 60} 이고 합은 113이다. 해결 가장 긴 증가하는 부분과 매우 유사한 문제이다. 이것도 마찬가지로! 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다. 최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다. 그러므로 일일이 구한 후 MAX 값을 찾아내면 끝! 알고리즘 DP로 풀었고, bottom-up 방식으로만 풀었다. DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자. 구현 java Bottom-Up 방식 ..

[백준(baekjoon) 11053] 가장 긴 증가하는 부분 수열 문제 백준 11053 n(1…1,000)과 n의 크기를 가진 수열이 주어질 때, 수열에서 증가하는 부분 수열 중 가장 긴 길이를 출력. 예시 : A = {10, 20, 10, 30, 20, 50} 인 경우, A = {10, 20, 30, 50} 이고 길이는 4이다. 해결 최소 길이 = 시작 값으로 끝나는 길이(초기) = 1이다. for(i = 1...n-1)문을 돌며 각 값으로 끝나는 부분 수열의 최대 길이를 차례대로 구해 저장한다. 이를 maxLength[i]라고 표현하겠다. 해당 값(input[i])으로 끝나는 증가하는 부분 수열은, 이전의 부분 수열 중 마지막 값이 자신보다 작은 경우 자신을 추가할 수 있다. 즉, 이러한 경우 길이는..

[백준(baekjoon) 2156] 포도주 시식 문제 백준 2156 n(1…10,000)개의 포도주가 있고 각 값이 주어진다. 포도주 선택 시 한잔을 모두 마셔야 하고, 연속으로 최대 2잔 마실 수 있을 때 최대 값을 구하라. 예시 : n = 6 { 6, 10, 13, 9, 8, 1 } => 정답은 1, 2, 4, 5{O, O, X, O, O, X}를 선택 할 때 33으로 최대다. 주의 : 각 포도잔의 값은 음이 아닌 정수이다. 해결 DP로 풀어야 한다는 전제하에 진행하였다. 난 DP 연습을 하고 있기 때문에. 단순하게 O, X 형식으로 하면 2^10000으로 2초를 훌쩍 넘긴다..! 그 다음에 여러 시도를 해봤었는데, (아래와 같은 것들?) 모두 시간초과가 떴다.. 3개씩 묶으면 그 안에 무조건 X하나..

[백준(baekjoon) 2193] 이친 수 문제 백준 2193 n(1…90)이 주어질 때, 길이가 n인 이친 수의 개수를 구하는 문제 이친 수 : 0으로 시작하지 않고, 11을 부문 문자열로 가지지 않는 이진 수 예시 : 1, 10, 101, 10101 해결 길이가 n인 이친 수는 길이가 n-1인 수의 끝자리를 기준으로 구할 수 있다. n-1의 끝자리가 0일 때 : 뒤에 0과 1을 붙일 수 있다. n-1의 끝자리가 1일 때 : 뒤에 0만 붙일 수 있다. (11은 불가하기 때문) 즉, 끝자리가 1, 0인 경우를 각각 저장해두고 이를 활용해 구하면 된다. n 예시 이친 수의 총 개수 끝자리가 0인 개수 끝자리가 1인 개수 1 1 1 0 1 2 10 1 1 0 3 100 101 2 1 1 4 1000 100..