다이나믹프로그래밍

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이문제는 가장 긴 증가하는 수열 + 가장 긴 감소하는 수열을 합쳐놓은 문제같다 ㅋㅋ 마침 두개 다 풀었고, 그래서 나는 1. 가장 긴 증가하는 수열 만들기 : dp 2. 가장 긴 감소하는 수열 만들기 : dp2 3. 합친 수열중에서 가장 길이가 긴 수열 값 구하기 -> dp3 테이블을 만들었다. # 11054 가장 긴 바이토닉 수열 n = int(input()) array = list(map(int, input()...

유형 : DP(다이나믹 프로그래밍) 배열을 뒤집어서 가장 긴 증가하는 수열을 찾는다 예전에 풀었던 문제 11722 가장 긴 감소하는 부분 수열과 똑같은 dp 문제이다. 다만 이번 문제에서는 제외할 병사의 수를 출력해야 하므로 n - dp의 최댓값 (= 가장 긴 수열의 길이) 를 출력해주어야 한다. https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 가장 긴 감소하는 부분 수..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..

다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 1. 탑다운 방식 (Top-down) 재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: # 이미 계산한 적 있으면 그대로 값을 반환한다. return d[x] d[x] = fibo(x-1) + fibo(x-2) return d[x] * 실행 결과 f(10)을 구하기 위해서 ..