DP

[문제] https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] [Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {..

[문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] 📌 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘 원소가 n개인 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 일반적으로 LIS의 길이를 ..

[문제] https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이] 우선 이 문제는 풀이 방식이 두 가지가 있다. 동적 프로그래밍을 이용해 풀기 조합을 이용해 풀기 동적 프로그래밍 풀이 1 2 3 4 5 1 1 2 3 4 5 2 X 1 3 6 10 3 X X 1 4 10 행이 n, 열이 m을 나타낼 때 1. n이 1인 경우 만들어지는 경우의 수는 m과 같다. 2. n이 2이상인 경우 num[n][m] = num[n][m - 1] + num[n -..

[문제] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [풀이] 이 문제는 피보나치 값이 아닌, 특정 값의 피보나치를 구하기 위해 호출되는 fibonaaci(0)과 fibonacci(1)의 호출 횟수를 구하는 것이다. 피보나치 문제는 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용하는 동적 계획법 으로 풀었다. fibonacci(n)을 구하기 위해서는 fibonacci(n-1)와 fibonacci(n-2)을 더해야 하기 때문에 fibonacci(n)을 호출할 경우 실행되는 fibonacci(0)과 fibonacci(1)은 '..

[문제] https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [풀이] 문제를 읽었을 때 딱 봐도 제곱 반복 수행 -> 문제 답 저장 후 해당 부분이 필요한 경우 저장된 결과를 사용 -> 동적 계획법!!! 그렇다면 이제 문제에 사용되는 규칙을 찾아야 한다. 0 1 2 3 4 5 6 7 8 1 0 1 2 3 1 5 6 7 8 2 0 1 2 3 1 2 3 4 2 3 0 1 2 3 1 2 3 0 0 4 0 1 2 3 1..

[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] 이 문제는 동적 프로그래밍으로 풀어야 하는 문제이다. 동적 프로그래밍의 개발절차는 문제의 사례에 대해 해답을 주는 재귀 관계식 정립 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례 해결 개발절차에 따르면 재귀 관계식을 정립해야 하기 때문에 우선 숫자 사이에서 규칙을 찾아보기로 했다. 5까지 직접 계산해 규칙을 찾아보니 이전 3개의 결과를 더한 숫자가 해당 숫자의 답이 되는 것을 발견했다. 이를 이용해 검증하기 위해 문제 예제에서 나온 7을 위의 규칙으로 계산해보니 44가..